Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

cryo75

Dijkstra's Algorithm

This topic is 5474 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, I have implemented the algorithm and it works fine when returning the shortest path from A to B. Now I need something more... How is it possible to return the 2nd, 3rd, 4th, etc... shortest paths using the same algorithm?? Thanks, Ivan

Share this post


Link to post
Share on other sites
Advertisement
This is a much harder (as in NP-complete) problem to solve. Let's consider this for a while. That would mean you must at some point choose a node that's not optimal, but how do you know when to choose that node in order to get the 2nd shortest path? You don't, so the only thing left would be to test all (wow). That is, you have to run the full algo for all nodes choosing one non-optimal node to finally find from which node you should choose the non-optimal node.


[edited by - amag on October 23, 2003 7:06:29 AM]

Share this post


Link to post
Share on other sites
Yeah that''s my problem and I don''t know how to solve it.

I have node A (eg. Paris) and node B (eg. Frankfurt). The 1st shortest path would be A to B over C (Cologne). So the algorithm gives me that one.

Now I want also the second shortest path (which will be a little longer than the 1st), example A to B over C and D (Bonn)...

Any ideas??

Share this post


Link to post
Share on other sites
Dijkstra''s algorithm requires you to remember the "best" path to a node, and then use this best path to reach another node, like this.

A -(m)-> B
A is reached in minimum n
B will be reached in minimum n+m from A

A variant of this would be to store a linked list of the n best paths, instead of just the best one.

A -(m)-> B
A is reached in {n1, n2, n3}
B will be reached in minimum {n1+m,n2+m,n3+m}

Now, how would this apply to the following case ?

A -(3)-> B
A -(5)-> C
C -(2)-> D
B -(1)-> C
B -(6)-> D

Start with A = {0}
Study node A : B = {3} C = {5}
Study node B : C = {4, 5} D = {9}
Study node C : D = {6, 7, 9}

Final state : A = {0} B = {3} C = {4, 5} D = {6, 7, 9}

So you''d have three ways of reaching D, of respecitve lengths 6, 7, 9. (Note : this only computes paths that go only once through any node).

From there, to find out where each came from: say we want to backtrace the second best path (length 7).

Test D -> B : 7-6 = 1, B = {3} so this didn''t come from B.
Test D -> C : 7-2 = 5, C = {4, 5} so this came from C.
Test C -> B : 5-1 = 4, B = {3} so this didn''t come from B.
Test C -> A : 5-5 = 0, A = {0} so this came from A.

Backtrace results in A -> C -> D which is of length 5+2 = 7.

A few hints :
- keep the list of possible paths sorted.
- do not use duplicate values.

Problems : this method will only find the "second best" path if it is LONGER than the best path. Generally, if more than one path is of a certain length, this method will only find one. But you could easily get past this by remembering from where each n1,n2,n3,... came.

ToohrVyk

Share this post


Link to post
Share on other sites
Hello cryo75,

One way to do what you whant is to for you to Mark the shost path with a very high cost for each node or remove the node form your check.

if as you say.
"I have node A (eg. Paris) and node B (eg. Frankfurt). The 1st shortest path would be A to B over C (Cologne). So the algorithm gives me that one."

then remove C (Cologne) form your vaild nodes to search and then the next path might include D (luxemburg).

Lord Bart

Share this post


Link to post
Share on other sites
It will mess up...

There was a similar problem where someone wanted Dijkstra's to randomly pick a path that's pretty good, turned out a good solution was to multiply all edge costs by 1+Rand(1) (in floating point) if you're just looking for similarly good paths this might do it for you, if you want absolute order, it is NP-Complete and will not be usefull in a real-time app unless the number of nodes in your graph is VERY small (less than 10).

George D. Filiotis

[b]I am a signature virus. Please add me to your signature so that I may multiply.

[edited by - symphonic on October 23, 2003 10:29:47 AM]

Share this post


Link to post
Share on other sites
I''m by no means an expert on this algorithm, but I think Symphonic has a good suggestion. If you take 10 searches with the random salt, you will likely get, on average, the 5 best paths. Then calculate their real "goodness", and sort.

Share this post


Link to post
Share on other sites
How about looking for the shortest route, and then finding the node which is ''closest'' to that route, i.e. I can go ABC, which is shortest, but I can also go ADC which is not shortest. If you found all those single-node alternate paths, you''d be able to pick the shortest one of them (producing the best path after the main one). I think it builds up to finding all the paths, but I don''t know.

The labelling nature of Dijikstra''s has to come into this somewhere. Hmm.....

Richard "Superpig" Fine
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.
Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4
ry. .ibu cy. .y''ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu
OpenGL is a language

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!