2
$\begingroup$

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the most prominent being probably the A* search algorithm. I know that this algorithm uses heuristics to make assumptions on the chances that one way would be shorter than the other. On every node the algorithm passes it needs a function that to get a probability of whether or not one path is shorter than the other ones. But what if no such assumptions can be made?

A bit more concrete, I want to find the shortest path from one wikipedia article to another one only using the links inside the articles. Is this possible without checking every possible order of articles? In my opinion every node has the same weight and every possible edge/link from a node has the same probability of ending in the shortest path. How can I possibly make any decisions which path to take?

I'm no mathematician but more of a designer/programmer so if you have any clue how to help me solve this problem please use a "maths-for-dummies" language.

$\endgroup$
  • $\begingroup$ Is this a question for the original stack exchange? $\endgroup$ – alex.jordan Jun 10 '14 at 20:09
  • $\begingroup$ This web site may be up to date as of about 2008.... but maybe it's no longer working. The person who created the site may be able to answer your question. $\endgroup$ – Michael Hardy Jun 10 '14 at 20:09
  • $\begingroup$ Another search algorithm considered by Barabssi was to keep going to the neighbour with the largest degree. $\endgroup$ – Sandeep Silwal Jun 11 '14 at 15:00
2
$\begingroup$

Breadth first search is how I would expect to handle this.

$\endgroup$
  • $\begingroup$ Seems very likely to me, too. $\endgroup$ – davidlowryduda Jun 10 '14 at 20:14
0
$\begingroup$

Thanks for your answers! I kept looking for solutions and found something very useful on stackoverflow. The answer is actually exactly what I expected. What I need is some function which makes an prediction for every node that is connected to the current on how long (relatively speaking) the total path will be. The post suggests keyword mapping or some other kind of guessing the similarity of two articles. Any other suggestions?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.