# Dijkstra's Algorithm

###
#1
Members - Reputation: **143**

Posted 22 October 2003 - 10:35 PM

###
#2
Members - Reputation: **152**

Posted 23 October 2003 - 12:05 AM

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

###
#3
Members - Reputation: **143**

Posted 23 October 2003 - 12:38 AM

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??

###
#4
Members - Reputation: **1591**

Posted 23 October 2003 - 01:00 AM

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

###
#5
Members - Reputation: **226**

Posted 23 October 2003 - 02:27 AM

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

###
#8
Members - Reputation: **313**

Posted 23 October 2003 - 03:29 AM

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]

###
#10
Members - Reputation: **1825**

Posted 23 October 2003 - 04:50 AM

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

###
#11
Members - Reputation: **211**

Posted 23 October 2003 - 06:18 AM

One paper on this:

http://citeseer.nj.nec.com/eppstein97finding.htm

It runs in O(m + n + log(n + k)), where m is the number of edges, and n is the number of edges.

I didn''t check it thoroughly, but I don''t belive it uses Dijkstra''a algorithm, so you would have to implement a completely new algorithm if you decide this could be useful.

###
#14
Members - Reputation: **152**

Posted 25 October 2003 - 04:22 AM

You also cannot remove a path or change the weights of the edges, since that would change the whole graph and you will most likely get different results.

I also think what Symphonic suggests might be a good idea, or at least you might want to look for a non-optimal solution on this one.

If you are certain you don''t have any cycles in your graph (not likely for a bus&train route) you can use a modified version of Dijkstra, where you don''t mark nodes as visited. That way you''ll get all paths and costs.

###
#16
Anonymous Poster_Anonymous Poster_*
Guests - Reputation:

Posted 25 October 2003 - 05:24 AM

quote:Why would anyone want a non-optimal bus/train route?Original post by cryo75

I need this algorithm for a bus & train route for quite a big area in Germany so there will be quite a lot of nodes in there.

###
#17
Members - Reputation: **152**

Posted 25 October 2003 - 05:59 AM

quote:

Why would anyone want a non-optimal bus/train route?

Beats me, maybe he just wants to give the user a choice?

quote:

He mentioned having quite a bit of nodes, thats what I was talking about.

Oh, sorry I thought you were refering to the main problem.

###
#18
Members - Reputation: **1412**

Posted 25 October 2003 - 03:13 PM

###
#19
Moderators - Reputation: **1648**

Posted 25 October 2003 - 07:29 PM

quote:Original post by cryo75

I need this algorithm for a bus & train route for quite a big area in Germany so there will be quite a lot of nodes in there.

Would there be a different algorithm instead of Dijkstra which does what I need?

Ivan

Yes, this problem is iso-morphic to the Salesman Problem, and as mentioned it is NP-complete _and_ the listing algorithm is already O(n

^{2}) - this is horribly time-consuming - O(n

^{2}!). If that is not bad enough, now you want to find the 3rd, 4th etc... this adds another O(n

^{2}) worst-case factor; you''re looking at a O(2 n

^{2}!) problem. If you can solve this problem in RT, you will be a rich man

I see two options; if the routes in question are fixed and do not change, or change very infrequently then pre-calculate all the common routes. Or, you cannot find _THE_ second best route, just another good one.

The base solution to your problem is simple to code though; whenver you test a node with Dijkstra algorithm, you check to see if the path matches the best path already found. If it does, you reject it and continue searching. For 3rd, 4th, you just check and reject against the 1st & 2nd, etc...

With some clever coding you can reduce the amoritized complexity of this check from n

^{2}to n, but it hardly seems worth the effort.

###
#20
Members - Reputation: **1412**

Posted 25 October 2003 - 09:17 PM

You might want to try variations as well - if the list is long, maybe only increase the cost of the last node or two on the path so you can get very simmilar but still different paths. If you want to do it in realtime, you might just return the best path then allow the person to choose which places they don''t want to go and give those nodes very high weights and recompute the path.