All-Pairs Shortest Paths: ======================== - We want to find the shortest paths between *every* pair of vertices u,v in G. One possible way to do this would be to simply run Dijkstra's algorithm once for each each vertex as the source, but this seems a bit inefficient. - How else can we do this? The idea is to start with the distances between each pair of vertices equal to the length of the edge between them (if there is one), or to "infinity" (if there is no edge), and then to update this distance little by little, by considering paths that use more and more intermediary vertices. (This is not an idea that's obvious, so don't worry if it doesn't make complete sense right now!) - More formally, for each pair i and j of vertices, we will keep track of a "distance" D_k[i,j] in the following way: D_k[i,j] = length of a shortest path from i to j that uses only vertices from {0,...,k} between i and j; Note that we are *not* saying that the path must use *all* of the vertices in {0,...,k}, or that it must use them in any specific order; all we're saying is that a path from i to j should only be considered if it does *not* use any of the vertices {k+1,...,n-1} (where the graph has n vertices). - Obviously, if we know D_{n-1}[i,j], then we have the length of a shortest path from i to j (because we're not restricting the path that can be used in any way). So how will we compute the values of D? We need initial conditions, a "base case" when we don't consider paths using *any* intermediate vertices: { 0 if i == j, D_{-1}[i,j] = { w(i,j) if i != j and (i,j) is in E, { oo otherwise. Then, we can compute the values of D_k[i,j] for k = 0,...,n-1, for each pair of vertices i,j. Once we know what it is we want to compute, the way to compute it is actually not too hard to figure out: consider a shortest path from i to j that uses only vertices from {0,...,k} between i and j. Either vertex k appears on that path or it doesn't. If it doesn't, then this is in fact a shortest path from i to j that uses only vertices from {0,...,k-1} between i and j, so D_k[i,j] = D_{k-1}[i,j]. If vertex k appears on the path, then consider the part of the path from i to k: this must be a shortest path from i to k that uses only vertices from {0,...,k-1} between i and k (and the same holds for the part of the path from k to j), so we must have D_k[i,j] = D_{k-1}[i,k] + D_{k-1}[k,j]. When we are computing the values of D_k from those stored in D_{k-1}, we don't know ahead of time which of these possibilities is the best, so we just let D_k[i,j] be the minimum of those two values. - This gives us the following algorithm, known as Floyd-Warshall's algorithm: FLOYD-WARSHALL( V, E ) for i := 0 to n-1 do for j := 0 to n-1 do if i == j then D_{-1}[i,j] := 0; else if (i,j) is in E then D_{-1}[i,j] := w(i,j); else D_{-1}[i,j] := oo; end if end for end for for k := 0 to n-1 do for i := 0 to n-1 do for j := 0 to n-1 do D_k[i,j] := D_{k-1}[i,j]; if D_{k-1}[i,k] + D_{k-1}[k,j] < D_k[i,j] then D_k[i,j] = D_{k-1}[i,k] + D_{k-1}[k,j]; end if end for end for end for END - Let's trace this algorithm on the following undirected graph: 1 (1)-----(2) | / | | 1 / | 4 | / | 3 | / | | / | (0)-----(3) 1 D_{-1}| 0 1 2 3 D_0| 0 1 2 3 D_1| 0 1 2 3 ---+------------ ---+------------ ---+------------ 0 | 0 4 1 1 0 | 0 4 1 1 0 | 0 4 1 1 | | | 1 | 0 1 oo 1 | 0 1 5 1 | 0 1 5 | | | 2 | 0 3 2 | 0 2 2 | 0 2 | | | 3 | 0 3 | 0 3 | 0 D_2| 0 1 2 3 D_3| 0 1 2 3 ---+------------ ---+------------ 0 | 0 2 1 1 0 | 0 2 1 1 | | 1 | 0 1 3 1 | 0 1 3 | | 2 | 0 2 2 | 0 2 | | 3 | 0 3 | 0 - Note something interesting about this algorithm: when we are computing the values of D_k[i,j], they can only change depending on the values of D_{k-1}[i,k] and D_{k-1}[k,j] (i.e., the values stored in row k and column k of the array), and those values themselves do *not* change (i.e., it is easy to show that D_k[i,k] = D_{k-1}[i,k] and D_k[k,j] = D_{k-1}[k,j] for all i,j)! So instead of keeping around n copies of the array (one for each value of k), we could simply replace the old values with the new ones at each iteration of the `k'-loop. - Also, this algorithm does not directly give us the actual paths between each pair of vertices. In order to get them, we can keep track of extra information: each time that we update D[i,j] for some k because we've found a shorter path, remember that the intermediate node used was `k' in a second array A[i,j]. Then, at the end, we can use this array to reconstruct the paths. Soon, we'll get back to this when we cover dynamic programming.