Find quickest way to get from wepage A to webpage B following links

Question

I'm looking for an algorithm to find the shortest path between two URL's, or two Wikipedia pages.

For example, the shortest way to get from the wikipedia article of Reddit to the article of Computer science is to follow the link to Science, where there is a link to Computer science.

Assume that all links are static, and that it is impractical to either load the entire graph nor traverse its entirety, is there a practical algorithm to find the shortest path, or prove that no path exists?

(I'm not sure if Dijkstra's is the best choice here, because the weight of every edge of the graph is 1)

Answer 1

I don't know, but check out this project to determine the distance between two wikipedia pages:

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

Answer 2

Here is a good place to start. I think Dijkstra's algorithm is probably your best bet if you want for certain the correct answer. If not you can use A* to find a faster aproximation

Answer 3

You might also try Breadth-First Search, and then stop as soon as you reach the destination. Actually, I think BFS is what you get from Dijkstra's when you constrain all edge weights to be 1, and you stop the search as you reach the point, but BFS is much easier conceptually than Dijkstra'sre. Remember that Dijkstra's is a single source all-paths, so you'd have to modify it if you use it for just from website A to website B.