Geek Answers Handbook

Find the fastest way to get the following links from wepage A to webpage B

I am looking for an algorithm to find the shortest path between two URLs or two Wikipedia pages.

For example, the shortest way to get an “Informatics” article from a Wikipedia Reddit article is to follow the link to “Science,” where there is a link to informatics.

Suppose that all links are static and that it is impractical to either load the entire graph or cross its entirety, is there a practical algorithm for finding the shortest path or to prove that the path does not exist?

(I'm not sure that Dykstra is the best choice here, because the weight of each edge of the graph is 1)

+4
source share
3 answers

I do not know, but check this project to determine the distance between the two Wikipedia pages:

http://www.netsoc.tcd.ie/~mu/wiki/

+2
source

Here is a good place to start. I think Dijkstra's algorithm is probably the best choice if you want the right answer to be the right one. If not, you can use A * to find a faster approximation

+2
source

You can also try Breadth-First Search and then stop as soon as you reach your destination. In fact, I think that BFS is what you get from Dijkstra when you limit all edge weights to 1 and you stop the search as you reach the goal, but BFS is much easier conceptually than Dijkstra'sre. Remember that Dijkstra is the only source of all paths, so you will have to modify it if you use it only from site A to website B.

+2
source

More articles:


All Articles