Archived

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

cryo75

Dijkstra's Algorithm

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
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
If it helps at all, there are algorithms that find the k shortest paths (somewhat) efficiently. This isn''t exactly what you want since it will return multiple paths and ties, but perhaps you can still utilize it for what you want.

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Actually using a priority-queue in Dijkstra is only an optimization to find the lowest-cost node faster. It wouldn''t help solve this problem ASFAIK.
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.
Why would anyone want a non-optimal bus/train route?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Does the bus/train schedule change often? If not, you could use a really really slow algorithm(like ''try every possible path up to the same length as the optimal path +3'') and just store that and then recompute it overnight or something whenever the schedules do change.

Share this post


Link to post
Share on other sites
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(n2) - this is horribly time-consuming - O(n2!). If that is not bad enough, now you want to find the 3rd, 4th etc... this adds another O(n2) worst-case factor; you''re looking at a O(2 n2!) 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 n2 to n, but it hardly seems worth the effort.

Share this post


Link to post
Share on other sites
Another thing you could do is just cost the nodes in the first path to be (original value)+(minimum value of all nodes / K) or something like that, so that they are less likely to get chosen (and if it still returns the original path, keep increasing the value until its a different path). If you want the first N paths, keep the original average cost around and continually increase the value of the costs until you get all the different paths you needed. It definitely isn''t optimal, but if you keep the value of the cost increase low, it should return reasonable results.

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.

Share this post


Link to post
Share on other sites
Im a bit confused as to why in a routing system you would want to find uniquely valued alternative routes. I can understand the need for finding alternatives to the optimal route, but surely such alternatives should be as short as possible?

I think the Eppstein technique also yields paths with cycles in them, which is probably not what you want.
If you want to find only simple(non-cyclic) paths you might wanna take a look at this:
http://citeseer.nj.nec.com/594094.html

Interestingly the Eppstein article mentions that the technique can be used for finding all paths shorter than some specific value. This might come in handy in practive if you are only interested in alternatives that are for example no worse than twice the optimal solution.


EDITED: removed a poor argument about NP stuff

[edited by - ziphnor on October 26, 2003 2:35:48 PM]

Share this post


Link to post
Share on other sites
Firstly, this problem is most definately not NP-complete.

One way of looking at it is that the 2nd best solution is one of 3 possibilities.

eg: best solution from a-g = a-b-c-d-e-f-g

2nd best solution can either be
1) best solution from a-g not passing through b
2) best solution from b-g, and 2nd-best solution from a-b. (which is very simple).
or
3) best solution from a-b, 2nd best solution from b-g (you can then use the same method to find the second-best solution from b to g.

so, using this method to find the path you would first calculate

best a-g without b.
2nd best a-b
best b-g without c.
2nd best b-c
best c-g without d.
2nd best c-d
best d-g without e.
2nd best d-e
best e-g without f
2nd best e-f
2nd best f-g

then simply find which of the above paths lost least distance over the best path, and u have your solution. (This can probably be heavily optimized... can''t be bothered at the moment tho)

so if d-g without e lost 1 point on d-g with e, and the rest lost more, then the solution would be:
a-b-c-d(newpath)g

if 2nd best c-d lost 1 point on best c-d, and the rest lost more, then the solution would be:
a-b-c(newpath)d-e-f-g

(b was chosen because it was the first step in the list)

So the worst case order is O(Djikstra * n). (I just got woken up and realised this but my sleepy brain can''t be bothered remembering or calcing Djikstra''s order. (n^3 or something like that).

Someone may want to verify this with more rigorous thought than I can supply. Goodnight.

Share this post


Link to post
Share on other sites
Which of the problems was that supposed to solve?

1. k shortest paths (ie w(p0) <= w(p1) <= w(p2)..)
2. k shortest loopless(simple) paths
3. k shortest paths or different lengths (ie w(p0) < w(p1) < w(p2)..)
4. k shortest simple paths of different lengths

The 2 first ones are definetly not NP-complete.

If your solution claims to find a solution to 3 or 4, then i think you have a problem when you say finding the second best path between a and b is simple. If you remove the edge (a,b) and find the best path from a -> b, then you might have a new path of the same weight as the edge (a,b), and i dont see how else you will find the second best path.

Personally im a bit of a slow thinker, i usually end up saying something wrong if i dont take alot of time to think things through, so i think ill have to think about it some more

[edited by - ziphnor on October 26, 2003 3:21:24 PM]

[edited by - ziphnor on October 26, 2003 3:23:48 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Ziphnor
If your solution claims to find a solution to 3 or 4, then i think you have a problem when you say finding the second best path between a and b is simple. If you remove the edge (a,b) and find the best path from a -> b, then you might have a new path of the same weight as the edge (a,b), and i dont see how else you will find the second best path.


Well, I think that in any situation you''ll end with a set of paths (i.e. more than one) for each total length.

You process every possible route through the network, and add it to the group. You pick any route from the shortest group as your optimum path. Any route from the same group can be called an ''alternate'' route; any route from the next group up can be called the ''second best'' route.

The most efficient solution would be one which eliminated all those ''alternate'' routes in each group, I think. I''m not sure how you can ''predict'' the length of a path - and thus skip it - until you''ve actually calculated it, though, so you''d end up processing all paths.

Though, as far as finding all paths goes, Dijikstra''s can help with that. The labelling system means that you pick a single start node and process the entire network, so you can get the shortest route from any given node to all other nodes by only labelling the network once for that given node. The time would thus be O(nD(n)) where n is the number of nodes and D(n) is the time taken by Dijikstra''s to label n nodes.

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