Hi I was wondering if there is an algorithm which would find shortest paths in graph. Let's say that I have a graph where there are couples of path from one vertex to another. Two or more of these paths have the same cost. How can I mark,find etc all shortest paths between these vertices ? As far as I konw Djikstra or Bellman-Ford algorithms will find shortest path but they "choose" only one. I hope that You'll understand my question :)
+3
A:
Dijkstra's algorithm gives you the cost to all the possible intermediate nodes, and the cost of the shortest path to the sink. You can get all the paths from source to sink by doing a depth first search from the sink to the source (going backwards), where you traverse an edge (backwards) only if the cost of that edge is equal to the difference between cost of the shortest path from the source to the two nodes. Of course you get the paths in reverse order, but reversing them is easy.
.
deinst
2010-08-09 16:05:51
Could You give me an example? I don't think I understood this correctly.I should start from sink vertex and do DFS, it is clear, however I don't understand the condition of traversing an edge
Berial
2010-08-09 22:58:09
Ok Start from the sink vertex, say your shortest path algorithm says that it is at distance 20 from the source. Say that there are three vertices leading to the sink, call them a, b, c, call the sink x. Say that a is at distance 18 from the source, and edge ax has weight 2, b is distance 17 from the source and bx has weight 4, and c is 19 from the source and cx has weight 1. This means that there are shortest paths from source to sink that end with ax and with cx. Use this procedure to list all the paths ending with ax, then all paths ending with cx.
deinst
2010-08-10 00:03:40
Ok I think that I managed to write this :) I must test my program and I levt You know if everything is OK
Berial
2010-08-11 11:36:42
A:
Take a look at Floyd-Warshall.
In computer science, the Floyd–Warshall algorithm (sometimes known as the WFI Algorithm or Roy–Floyd algorithm) is a graph analysis algorithm for finding shortest paths in a weighted graph (with positive or negative edge weights). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. The algorithm is an example of dynamic programming.
T.K.
2010-08-09 17:41:56
How does this help? The question is about all shortest paths between given two vertices. There is only one pair.
Moron
2010-08-09 17:45:22
@Moron - Oh, my mistake. I was under the impression that Berial was saying that those algorithms only found the shortest between any two nodes, rather than all equally short paths between two specific nodes. Floyd-Warshall will find all shortest paths in a graph, rather than all shortest paths between two vertexes.
T.K.
2010-08-09 22:50:14