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]

# Dijkstra's Algorithm

Started by cryo75, Oct 22 2003 10:35 PM

32 replies to this topic

Sponsor:

###
#22
Members - Reputation: **142**

Posted 26 October 2003 - 05:41 AM

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.

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.

###
#23
Members - Reputation: **122**

Posted 26 October 2003 - 08:20 AM

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]

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]

###
#25
Staff Emeritus - Reputation: **1825**

Posted 26 October 2003 - 12:39 PM

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

###
#26
Members - Reputation: **142**

Posted 26 October 2003 - 04:19 PM

Following on from my previous solution, which did not take into account looping paths.

Assuming all paths are bi-directional, I think the shortest looping path could be found by:

For every node, Find the shortest path between [start] and [finish] that passes through that node, and add 2 * the shortest edge off that node.

The smallest solution here will be the shortest looping path.

(If paths are not all bi-directional, modify above to instead add the shortest loop about the node.

BTW, is the path a-b-c-d-e-g-f-g (note the repeated g) valid as a path from a to g? If so, you''ll have to test the start and finish nodes too.

Unfortunately, my solutions are all for the second-shortest path.

I think, using my solution to find the x''th shortest loopless path would be order O(Dijkstra * n * x!). The factorial makes this rather nasty for high x. There''s probably a good way around this.

Assuming all paths are bi-directional, I think the shortest looping path could be found by:

For every node, Find the shortest path between [start] and [finish] that passes through that node, and add 2 * the shortest edge off that node.

The smallest solution here will be the shortest looping path.

(If paths are not all bi-directional, modify above to instead add the shortest loop about the node.

BTW, is the path a-b-c-d-e-g-f-g (note the repeated g) valid as a path from a to g? If so, you''ll have to test the start and finish nodes too.

Unfortunately, my solutions are all for the second-shortest path.

I think, using my solution to find the x''th shortest loopless path would be order O(Dijkstra * n * x!). The factorial makes this rather nasty for high x. There''s probably a good way around this.

###
#27
Members - Reputation: **122**

Posted 26 October 2003 - 08:26 PM

quote:Original post by superpigquote: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

Every possible (simple) path through the graph between two points, must be of exponential size. And i fail to see how Dijkstraa can help you, as it can only give you the n-1 optimal paths to the n-1 other nodes in the graph.(but perhaps i misunderstood you?)

To Kryollan:

quote:

BTW, is the path a-b-c-d-e-g-f-g (note the repeated g) valid as a path from a to g?

In problem 3 its valid, in 4 its not(because its not simple)

[edited by - ziphnor on October 27, 2003 3:26:44 AM]

[edited by - ziphnor on October 27, 2003 3:32:53 AM]

###
#28
Crossbones+ - Reputation: **1911**

Posted 26 October 2003 - 09:28 PM

besides all the technicality, isn''t the timetables, projected traffic congestions, availability actually as important as the shortest path? Unless the buses in Frankfurt run every 3 minutes, are on time, and run all the way through the night, unlike here, in Oxford

###
#29
Members - Reputation: **142**

Posted 26 October 2003 - 09:36 PM

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.

I''m assuming here that an alternative path than the one given by Djikstra, but with the same weight, qualifies as a 2nd-best path. (Technically it''s 1st equal, but I am assuming that calling it 2nd would be what is desired by cryo75.)

In a real-world (eg train routes) situation it is incredibly unlikely (usually impossible) that any two paths that cross a different set of edges (or the same set but differrent amounts of times on some edges) would be equal, since the distance between the Nice and Paris main terminals isn''t rational (Unless some extraneous forces were at work constructing the french train network .

###
#30
Members - Reputation: **143**

Posted 26 October 2003 - 09:40 PM

Thanks to everybody for the suggestions. As I see it, there''s no simple way to get n shortest paths using Dijkstra, although I''ve got to use this algorithm as I have all the distances between each nodes.

Furthermore, to reply to some of the posts. I need n shortest paths to give the user a choice to select which path to use. And I''m not interested about time, schedules or timetables... but just paths.

Ivan

Furthermore, to reply to some of the posts. I need n shortest paths to give the user a choice to select which path to use. And I''m not interested about time, schedules or timetables... but just paths.

Ivan

###
#31
Members - Reputation: **214**

Posted 26 October 2003 - 09:46 PM

Since I am way too tired and not having read through all things I''ll still give an attempt to help you out.

Assuming your paths are connected through waypoints. That is, *not*, drawing a path through unknowns. Then you get the shortest path. Remove the path (mark it) run again etc... Now when you are finished there will be no way of reaching the target. With the accumulated list you do a sort according to length. Think of vectors. Then you will have a full list of paths to the target with distance. Then you can build on this of course (which I will not go into here) to allow the AI to choose which way is more economical. The *economy* is decided on what requirements your map has.

Hope this gives some ideas.

____________________________________________________________

Try RealityRift at www.planetrift.com

Feel free to comment, object, laugh at or agree to this. I won''t engage in flaming because of what I have said.

I could be wrong or right but the ideas are mine.

Assuming your paths are connected through waypoints. That is, *not*, drawing a path through unknowns. Then you get the shortest path. Remove the path (mark it) run again etc... Now when you are finished there will be no way of reaching the target. With the accumulated list you do a sort according to length. Think of vectors. Then you will have a full list of paths to the target with distance. Then you can build on this of course (which I will not go into here) to allow the AI to choose which way is more economical. The *economy* is decided on what requirements your map has.

Hope this gives some ideas.

____________________________________________________________

Try RealityRift at www.planetrift.com

Feel free to comment, object, laugh at or agree to this. I won''t engage in flaming because of what I have said.

I could be wrong or right but the ideas are mine.

###
#32
Members - Reputation: **122**

Posted 27 October 2003 - 05:53 AM

quote:

I'm assuming here that an alternative path than the one given by Djikstra, but with the same weight, qualifies as a 2nd-best path. (Technically it's 1st equal, but I am assuming that calling it 2nd would be what is desired by cryo75.)

Okay, then i think your method is probably sound enough, and i know there are some decently fast algorithms out there for this problem.(just search for k shortest simple( or loopless) paths).

I was just under the impression that what was being requested was a solution to 3 or 4(not that i understood why you would want a strictly longer alternate path ).

I agree that in the real world there will probably be very few paths with exactly equal distances, but it would be "prettier" to have a more general solution

To Cryo75:

I actually dont think the Eppstein technique is that complicated, but it can yield alternatives paths that contain cycles(but you can just remove those and hope there are some left .

Btw, were you actually in need of the 2nd best simple path striclty longer than the optimal one, or just the second best simple path?

[edited by - ziphnor on October 27, 2003 12:54:42 PM]

###
#33
Members - Reputation: **143**

Posted 28 October 2003 - 12:55 AM

I think I came up with an idea on how to overcome the problem. Look at

the following:

A

B C F E

F 25 G

21 F

22

I want to go from A to F, so I have:

ACF = 21

AF = 25

AEGF = 22

Dijkstra will give me ACF which is correct. But from the above we see

that A has 4 neighbours which can lead to F. So what I could do is

iterate through each of A''s four neighbours like this:

Iteration 1: Set B as not visited, C, F, E as visited. Run Dijkstra.

Will give me no results.

Iteration 2: Set C as not visited, B, F, E as visited. Run Dijkstra.

Will give me ACF, store the results.

Iteration 3: Set F as not visited, B, C, E as visited. Run Dijkstra.

Will give AF, store the results.

Iteration 4: Set E as not visited, B, C, F as visited. Run Dijkstra.

Will give me AGEF, store the results.

Sort the results according to length, ie. 21, 22, 25 and return the

paths to each and every one.

I think this should work.

Ivan

the following:

A

B C F E

F 25 G

21 F

22

I want to go from A to F, so I have:

ACF = 21

AF = 25

AEGF = 22

Dijkstra will give me ACF which is correct. But from the above we see

that A has 4 neighbours which can lead to F. So what I could do is

iterate through each of A''s four neighbours like this:

Iteration 1: Set B as not visited, C, F, E as visited. Run Dijkstra.

Will give me no results.

Iteration 2: Set C as not visited, B, F, E as visited. Run Dijkstra.

Will give me ACF, store the results.

Iteration 3: Set F as not visited, B, C, E as visited. Run Dijkstra.

Will give AF, store the results.

Iteration 4: Set E as not visited, B, C, F as visited. Run Dijkstra.

Will give me AGEF, store the results.

Sort the results according to length, ie. 21, 22, 25 and return the

paths to each and every one.

I think this should work.

Ivan