FInding All Shortest Paths Between Two Vertices

问题:

Given a directed graph G=(V,E), two vertices s, t and two weight functions w1, w2, I need to find the shortest path from s to t by w2 among all the shortest paths between s to t by w1. First of all , how could I find all the shortest paths between two vertices s and t? Dijkstra's algorithm helps us find shortest path from a vertex to to every other accessible vertex, is it possible to modify it in order to get all the shortest paths between two vertices?

回答1:

I will expand on comments to the question. The problem is, for some graphs, you can have an exponential number of shortest paths between two vertices, for example

    o   o         o
   / \ / \       / \
u o   o   o ... o   o v
   \ / \ /       \ /
    o   o         o

Here you have O(2^|V|) shortest paths between u and v.

The better approach would be the one proposed by @n.m. in the comments:

Simply use a weight function w=(w1, w2), with component-wise addition and lexicographical ordering.

The lexicographical addition is straightforward: you define a new weight function to be w(e)=(w1(e), w2(e)) (i.e. a vector of the weights using the given two weight functions).

Then you define the addition operation (you have to have one for a weight function target set):

w = (w1, w2)
W = (W1, W2)
w + W := (w1 + W1, w2 + W2)

For our case: you have a shortest path according to the weight function w = (w1, w2), p0. Let's prove it will be the shortest path according to w2 among the shortest paths according to w1.

Basically it means that for every path p w(p) >= w(p0) which means that either w1(p) > w1(p0) (so p is not among the shortest according to w1) or w1(p) == w1(p0) and w2(p) >= w2(p0) so the path p is amongst the shortest according to w1 but it is not shorter according to w2. That means that p0 is the shortest according to w2 amongst the shortest according to w1.

回答2:

This is quite strightforward. Completely from Wikipedia:

A more general problem would be to find all the shortest paths between source and target (there might be several different ones of the same length). Then instead of storing only a single node in each entry of previous[] we would store all nodes satisfying the relaxation condition. For example, if both r and source connect to target and both of them lie on different shortest paths through target (because the edge cost is the same in both cases), then we would add both r and source to previous[target]. When the algorithm completes, previous[] data structure will actually describe a graph that is a subset of the original graph with some edges removed. Its key property will be that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph will be the shortest path between those nodes in the original graph, and all paths of that length from the original graph will be present in the new graph. Then to actually find all these shortest paths between two given nodes we would use a path finding algorithm on the new graph, such as depth-first search.

In other words, after Dijkstra terminates, you should be able to know all the previous nodes for the nodes on the shortest path from s to t, and do a backward BFS/DFS with these edges would give you all the shortest pathes.

回答3:

Using Dynamic Programming this can be efficiently solved for with the Floyd-Warshall algorithm which is designed specifically to find all possible shortest paths from s to t. Floyd-Warshall does have an improvement over Dijkstra's when you want to handle negative edge weights (Dijkstra's won't handle negative weights), however keep in mind that Floyd-Warshall's Algorithm cannot deal with negative cycles.

From Wikipedia:

"The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with only Θ(|V|³) comparisons in a graph. This is remarkable considering that there may be up to Ω(|V|²) edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal."

回答4:

Dijkstra is exactly what you are looking for. The resulting values get saved to a Lengths structure, where each vertex is associated with a numeric value (the distance between vertex s and every other vertex accessible from x). Then just access the respective value for your t vertex in that structure. Search for implementations. It's usually as simple as accessing the t position of an array, given that you can represent your vertex with an int.