# All-pairs shortest path

###### All-pairs shortest path
ECE 250 Algorithms and Data Structures Allpairs shortest path Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Allpairs Shortest Path 2 Outline This topic will: – Review Dijkstra’s algorithm for finding a shortest path – Consider what happens if we want to find all shortest paths – We will look at the FloydWarshall algorithm for: • Finding these shortest distances • Finding the paths corresponding to these distances – We conclude by finding the transitive closureAllpairs Shortest Path 3 5.1 Background Dijkstra’s algorithm finds the shortest path between two nodes 2 – Run time:  V  If we wanted to find the shortest path between all pairs of nodes, we could apply Dijkstra’s algorithm to each vertex: – Run time:  V E ln V  2 3 EV  In the worst case, if , the run time is VV ln  Allpairs Shortest Path 4 5.1 Background Any algorithm that finds the shortest path between all pairs must consider, each pair of vertices; therefore, a lower bound on the execution would be 2  V  Now, Dijkstra’s algorithm has the following run times: – Best case: 2 If EV  , running Dijkstra for each vertex is VV ln   – Worst case: 2 3 EV  If , running Dijkstra for each vertex isVV ln  Allpairs Shortest Path 5 5.1.1 Problem 3 o V ln V Question: for the worst case, can we find a algorithm  We will look at the FloydWarshall algorithmAllpairs Shortest Path 6 5.1.2 Strategy First, let’s consider only edges that connect vertices directly: 0 If ij   (0) d w If there is an edge from i to j  i,, j i j   Otherwise  Here, w is the weight of the edge connecting vertices i and j i,j (0) (0) dd – Note, this can be a directed graph; i.e., it may be that i,, j j i In C++, we would define a twodimensional array double dnumverticesnumvertices;Allpairs Shortest Path 7 5.1.2 Strategy Consider this graph of seven vertices 0 0  – The edges defining the values d and d are highlighted 5,3 6,7Allpairs Shortest Path 8 5.1.2 Strategy Suppose now, we want to see whether or not the path going through vertex v is shorter than a direct edge 1 0 0 0  d  d d – Is 5,3 5,1 1,3 0 0 0  – Is d  d d 6,7 6,1 1,7Allpairs Shortest Path 9 5.1.2 Strategy 1  Thus, for each pair of edges, we will define d by calculating: ij , 1 0 0 0  d min d ,d d  i, j i, j i,1 1, jAllpairs Shortest Path 10 5.1.2 Strategy 10  10  dd Note that and ; thus, we need just run the dd ii ,1 ,1 1,jj 1, algorithm for each pair of vertices: for ( int i = 0; i numvertices; ++i ) for ( int j = 0; j numvertices; ++j ) dij = std::min( dij, di0 + d0j ); Allpairs Shortest Path 11 5.1.2 The General Step k1  Define d as the shortest distance, but only allowing intermediate ij , visits to vertices v , v , …, v 1 2 k–1 – Suppose we have an algorithm that has found these values for all pairsAllpairs Shortest Path 12 5.1.2 The General Step k  How could we find d ; that is, the shortest path allowing ij , intermediate visits to vertices v , v , …, v , v 1 2 k–1 kAllpairs Shortest Path 13 5.1.2 The General Step With v , v , …, v as intermediates, have assumed we have found 1 2 k–1 the shortest paths from v to v , v to v and v to v i j i k k j – The only possible shorter path including v would be the path from v to k i v continuing from there to v k j kk1k1k1 d min d ,d d Thus, we calculate  i, j i, j i,k k, jAllpairs Shortest Path 14 5.1.2 The General Step Finding this for all pairs of vertices gives us all shortest paths from v to v possibly going through vertices v , v , …, v i j 1 2 k kk1 kk1  dd dd – Again, note that and do not change under this step k,, j k j i,, k i k – To simplify, the notation, we can remove the superscriptsAllpairs Shortest Path 15 5.1.2 The General Step Thus, the calculation is straight forward: for ( int i = 0; i numvertices; ++i ) for ( int j = 0; j numvertices; ++j ) dij = std::min( dij, dik + dkj ); Allpairs Shortest Path 16 5.1.2 The FloydWarshall Algorithm Thus, we have found the FloydWarshall algorithm: double dnumverticesnumvertices; // Initialize the matrix d: Theta(V2) // ... // Run FloydWarshall for ( int k = 0; k numvertices; ++k ) for ( int i = 0; i numvertices; ++i ) for ( int j = 0; j numvertices; ++j ) dij = std::min( dij, dik + dkj ); 3  V Run time Allpairs Shortest Path 17 5.1.2 The FloydWarshall Algorithm Question: we’ve already argued that at step k, d and d remain i,k k,j unchanged, would you want to avoid the calculation if i = k or j = k // Run FloydWarshall for ( int k = 0; k numvertices; ++k ) for ( int i = 0; i numvertices; ++i ) for ( int j = 0; j numvertices; ++j ) if ( i = k j = k ) dij = std::min( dij, dik + dkj ); Would you perform  V checks to avoid a operation  1 Allpairs Shortest Path 18 5.1.2 The FloydWarshall Algorithm In such a case, if you must absolutely minimize the iterations: // Run FloydWarshall for ( int k = 0; k numvertices; ++k ) for ( int i = 0; i k; ++i ) for ( int j = 0; j k; ++j ) dij = std::min( dij, dik + dkj ); for ( int j = k + 1; j numvertices; ++j ) dij = std::min( dij, dik + dkj ); for ( int i = k + 1; i numvertices; ++i ) for ( int j = 0; j k; ++j ) dij = std::min( dij, dik + dkj ); for ( int j = k + 1; j numvertices; ++j ) dij = std::min( dij, dik + dkj ); Allpairs Shortest Path 19 Example Consider this graphAllpairs Shortest Path 20 Example The adjacency matrix is 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.554 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  This would define our matrix D = (d ) ijAllpairs Shortest Path 21 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.554 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  We would start: (2, 3) → (2, 1, 3) 0.191 ≯ 0.465 + 0.101 Allpairs Shortest Path 22 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.554 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  We would start: (2, 4) → (2, 1, 4) 0.192 ≯ 0.465 + 0.142 Allpairs Shortest Path 23 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.554 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  We would start: (2, 5) → (2, 1, 5) 0.587 ≯ 0.465 + 0.277 Allpairs Shortest Path 24 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.554 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  Here is a shorter path: (3, 2) → (3, 1, 2) 0.554 0.245 + 0.100 = 0.345 Allpairs Shortest Path 25 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  We update the table (3, 2) → (3, 1, 2) 0.554 0.245 + 0.100 = 0.345 Allpairs Shortest Path 26 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  And a second shorter path: (3, 5) → (3, 1, 5) 0.931 0.245 + 0.277 = 0.522Allpairs Shortest Path 27 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.522  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  We update the tableAllpairs Shortest Path 28 Example With the first pass, k = 1, we attempt passing through vertex v 1 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.554 0 0.333 0.931  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  Continuing: (4, 2) → (4, 1, 2) 0.668 ≯ 1.032 + 0.100 In fact, no other shorter paths through vertex v exist 1Allpairs Shortest Path 29 Example With the next pass, k = 2, we attempt passing through vertex v 2 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.522  1.032 0.668 0.656 0 0.151   0.867 0.119 0.352 0.398 0  There are three shorter paths: (5, 1) → (5, 2, 1) 0.867 0.119 + 0.465 = 0.584 (5, 3) → (5, 2, 3) 0.352 0.119 + 0.191 = 0.310 (5, 4) → (5, 2, 4) 0.398 0.119 + 0.192 = 0.311Allpairs Shortest Path 30 Example With the next pass, k = 2, we attempt passing through vertex v 2 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.522  1.032 0.668 0.656 0 0.151   0.584 0.119 0.310 0.311 0  We update the tableAllpairs Shortest Path 31 Example With the next pass, k = 3, we attempt passing through vertex v 3 0 0.100 0.101 0.142 0.277   0.465 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.522  1.032 0.668 0.656 0 0.151   0.584 0.119 0.310 0.311 0  There are three shorter paths: (2, 1) → (2, 3, 1) 0.465 0.191 + 0.245 = 0.436 (4, 1) → (4, 3, 1) 1.032 0.656 + 0.245 = 0.901 (5, 1) → (5, 3, 1) 0.584 0.310 + 0.245 = 0.555Allpairs Shortest Path 32 Example With the next pass, k = 3, we attempt passing through vertex v 3 0 0.100 0.101 0.142 0.277   0.436 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.522  0.901 0.668 0.656 0 0.151   0.555 0.119 0.310 0.311 0  We update the tableAllpairs Shortest Path 33 Example With the next pass, k = 4, we attempt passing through vertex v 4 0 0.100 0.101 0.142 0.277   0.436 0 0.191 0.192 0.587   0.245 0.345 0 0.333 0.522  0.901 0.668 0.656 0 0.151   0.555 0.119 0.310 0.311 0  There are two shorter paths: (2, 5) → (2, 4, 5) 0.587 0.192 + 0.151 (3, 5) → (3, 4, 5) 0.522 0.333 + 0.151Allpairs Shortest Path 34 Example With the next pass, k = 4, we attempt passing through vertex v 4 0 0.100 0.101 0.142 0.277   0.436 0 0.191 0.192 0.343   0.245 0.345 0 0.333 0.484  0.901 0.668 0.656 0 0.151   0.555 0.119 0.310 0.311 0  We update the tableAllpairs Shortest Path 35 Example With the last pass, k = 5, we attempt passing through vertex v 5 0 0.100 0.101 0.142 0.277   0.436 0 0.191 0.192 0.343   0.245 0.345 0 0.333 0.484  0.901 0.668 0.656 0 0.151   0.555 0.119 0.310 0.311 0  There are three shorter paths: (4, 1) → (4, 5, 1) 0.901 0.151 + 0.555 = 0.706 (4, 2) → (4, 5, 2) 0.668 0.151 + 0.119 = 0.270 (4, 3) → (4, 5, 3) 0.656 0.151 + 0.310 = 0.461Allpairs Shortest Path 36 Example With the last pass, k = 5, we attempt passing through vertex v 5 0 0.100 0.101 0.142 0.277   0.436 0 0.191 0.192 0.343   0.245 0.345 0 0.333 0.484  0.706 0.270 0.461 0 0.151   0.555 0.119 0.310 0.311 0  We update the tableAllpairs Shortest Path 37 Example Thus, we have a table of all shortest paths: 0 0.100 0.101 0.142 0.277   0.436 0 0.191 0.192 0.343   0.245 0.345 0 0.333 0.484  0.706 0.270 0.461 0 0.151   0.555 0.119 0.310 0.311 0 Allpairs Shortest Path 38 What Is the Shortest Path This algorithm finds the shortest distances, but what are the paths corresponding to those shortest distances – Recall that with Dijkstra’s algorithm, we could find the shortest paths by recording the previous node – You would start at the end and work your way back…Allpairs Shortest Path 39 What Is the Shortest Path Suppose the shortest path from v to v is as follows: i jAllpairs Shortest Path 40 What Is the Shortest Path Is this path not the (v , v ) followed by the shortest path from v to v i 5 5 j – If there was a shorter path from v to v through v that didn’t follow v , i j 5 2 v , etc., then we would also find a shorter path from v to v 13 5 jAllpairs Shortest Path 41 What Is the Shortest Path Now, suppose we have the shortest path from v to v which passes i j through the vertices v , v , …, v 1 2 k–1 – In this example, the next vertex in the path is v 5Allpairs Shortest Path 42 What Is the Shortest Path What if we find a shorter path passing through v k – In this example, all we’d have to do is now remember that the new path has v as the second node—the rest of the path would be recursively 4 stored as the shortest path from v to v 4 jAllpairs Shortest Path 43 What Is the Shortest Path In this case, let us store the shortest path moving forward:  If ij   p j If there is an edge from i to j  ij ,   Otherwise  Now, if we find a shorter path, update the value – This matrix will store the next vertex in the list in the shortest path starting at vertex v iAllpairs Shortest Path 44 What Is the Shortest Path Thus, if we ever find a shorter path, update it the next node: pp i,, j i k unsigned int pnumverticesnumvertices; // Initialize the matrix p: Theta(V2) // ... // Run FloydWarshall for ( int k = 0; k numvertices; ++k ) for ( int i = 0; i numvertices; ++i ) for ( int j = 0; j numvertices; ++j ) if ( dij dik + dkj ) pij = pik; dij = dik + dkj; Allpairs Shortest Path 45 Example In our original example, initially, the next node is exactly that:  2 3 4 5   1 3 4 5   1 2 4 5  1 2 3 5   1 2 3 4  This would define our matrix P = (p ) ijAllpairs Shortest Path 46 Example With the first pass, k = 1, we attempt passing through vertex v 1  2 3 4 5   1 3 4 5   1 2 4 5  1 2 3 5   1 2 3 4  There are two shorter paths: (3, 2) → (3, 1, 2) 0.554 0.245 + 0.100 (3, 5) → (3, 1, 5) 0.931 0.245 + 0.277Allpairs Shortest Path 47 Example With the first pass, k = 1, we attempt passing through vertex v 1  2 3 4 5   1 3 4 5   1 1 4 1  1 2 3 5   1 2 3 4  We update each of theseAllpairs Shortest Path 48 Example After all the steps, we end up with the matrix P = (p ): i,j  2 3 4 5   3 3 4 4   1 1 4 4  5 5 5 5   2222 Allpairs Shortest Path 49 Example These are all the adjacent edges that are still the shortest distance  2 3 4 5   3 3 4 4   1 1 4 4  5 5 5 5   2222  For each of these, p = j i,j In all cases, the shortest distance from vertex 0 is the direct edgeAllpairs Shortest Path 50 Example From vertex v , p = 3 and p = 4; we go directly to vertices v and v 2 2,3 2,4 3 4  2 3 4 5   3 3 4 4   1 1 4 4  5 5 5 5   2222  But p = 3 and p = 1; 2,1 3,1 the shortest path to v is (2, 3, 1) 1 Also, p = 4 and p = 5; 2,5 4,5 the shortest path to v is (2, 4, 5) 5Allpairs Shortest Path 51 Example From vertex v , p = 1 and p = 4; we go directly to vertices v and v 3 3,1 3,4 1 4  2 3 4 5   3 3 4 4   1 1 4 4  5 5 5 5   2222  But p = 1 and p = 2; 3,2 1,2 the shortest path to v is (3, 1, 2) 2 Also, p = 4 and p = 5; 3,5 4,5 the shortest path to v is (3, 4, 5) 5Allpairs Shortest Path 52 Example From vertex v , p = 5; we go directly to vertex v 4 4,5 5  2 3 4 5   3 3 4 4   1 1 4 4  5 5 5 5   2222  But p = 5, p = 2, p = 3, p = 1; 4,1 5,1 2,1 3,1 the shortest path to v is (4, 5, 2, 3, 1) 1Allpairs Shortest Path 53 Example From vertex v , p = 2; we go directly to vertex v 5 5,2 2  2 3 4 5   3 3 4 4   1 1 4 4  5 5 5 5   2222  But p = 2 and p = 4; 5,4 2,4 the shortest path to v is (5, 2, 4) 4Allpairs Shortest Path 54 Comment CLRS implements it backward, so that a matrix P stores the predecessors—similar to Dijkstra’s algorithm  If ij   pp p i If there is an edge from i to j i,, j k j  ij ,   Otherwise  Another approach is to store the value kAllpairs Shortest Path 55 Which Vertices are Connected Finally, what if we only care if a connection exists – Recall that with Dijkstra’s algorithm, we could find the shortest paths by recording the previous node – In this case, can make the observation that: A path from v to v exists if either: i j A path exists through the vertices from v to v , or 1 k–1 A path, through those same nodes, exists from v to v and i k a path exists from v to v k jAllpairs Shortest Path 56 Which Vertices are Connected The transitive closure is a Boolean graph: bool tcnumverticesnumvertices; // Initialize the matrix tc: Theta(V2) // ... // Run FloydWarshall for ( int k = 0; k numvertices; ++k ) for ( int i = 0; i numvertices; ++i ) for ( int j = 0; j numvertices; ++j ) tcij = tcij (tcik tckj); Allpairs Shortest Path 57 Example Consider this directed graph – Each pair has only one directed edge – Vertex v is a source and 1 v is a sink 4 We will apply all three matrices – Shortest distance – Paths – Transitive closureAllpairs Shortest Path 58 Example We set up the three initial matrices 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2  2 4 6 F T T F T F   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    10 7 0 34 F F T T F F Allpairs Shortest Path 59 Example At step 1, no path leads to v , so 1 no shorter paths could be found passing through v 1 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2  2 4 6 F T T F T F   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    10 7 0 34 F F T T F F Allpairs Shortest Path 60 Example At step 2, we find: – A path (3, 2, 7) of length 14 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2  2 4 6 F T T F T F   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    10 7 0 34 F F T T F F Allpairs Shortest Path 61 Example At step 2, we find: – A path (3, 2, 7) of length 14 We update d = 14, p = 2 and c = T 3,7 3,7 3,7 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2 14  2 4 6 2 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    10 7 0 34 F F T T F F Allpairs Shortest Path 62 Example At step 3, we find: – A path (7, 3, 2) of length 19 – A path (7, 3, 6) of length 12 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2 14  2 4 6 2 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    10 7 0 34 F F T T F F Allpairs Shortest Path 63 Example At step 3, we find: – A path (7, 3, 2) of length 19 – A path (7, 3, 6) of length 12 We update d = 19, p = 3 and c = T 7,2 7,2 7,2 d = 12, p = 3 and c = T 7,6 7,6 7,6 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2 14  2 4 6 2 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    19 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 64 Example At step 4, there are no paths out of vertex v , so we are finished 4 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2 14  2 4 6 2 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    19 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 65 Example At step 5, there is one incoming edge from v to v , and it doesn’t 1 5 make any paths out of vertex v 1 any shorter... 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2 14  2 4 6 2 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    19 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 66 Example At step 6, we find: – A path (1, 6, 2) of length 6 – A path (1, 6, 4) of length 7 – A path (1, 6, 7) of length 4 – A path (3, 6, 2) of length 7 – A path (3, 6, 7) of length 5 – A path (7, 3, 6, 2) of length 17 0 11 7 9 8 1 5 2 3 4 5 6 7 T T T T T T    0 5 547 F F T F F T    9 0 7 2 14  2 4 6 2 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    19 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 67 Example At step 6, we find: – A path (1, 6, 2) of length 6 – A path (1, 6, 4) of length 7 – A path (1, 6, 7) of length 4 – A path (3, 6, 2) of length 7 – A path (3, 6, 7) of length 5 – A path (7, 3, 6, 2) of length 17 0 6 7 7 8 1 4 6 3 6 5 6 6 T T T T T T    0 5 547 F F T F F T    7 0 7 2 5  6 4 6 6 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    17 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 68 Example At step 7, we find: – A path (2, 7, 3) of length 15 – A path (2, 7, 6) of length 17 – A path (6, 7, 3) of length 13 0 6 7 7 8 1 4 6 3 6 5 6 6 T T T T T T    0 5 547 F F T F F T    7 0 7 2 5  6 4 6 6 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 6 0 3 2 4 7 F T F T F T    17 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 69 Example Finally, at step 7, we find: – A path (2, 7, 3) of length 15 – A path (2, 7, 6) of length 17 – A path (6, 7, 3) of length 13 0 6 7 7 8 1 4 6 3 6 5 6 6 T T T T T T    0 15 5 17 5 7 4 7 7 F T T F T T    7 0 7 2 5  6 4 6 6 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 13 6 0 3 2 7 4 7 F T T T F T    17 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 70 Example Note that: – From v we can go anywhere 1 – From v we can go anywhere but v 5 1 – We go between any of the vertices in the set v , v , v , v 2 3 6 7 – We can’t go anywhere from v 4 0 6 7 7 8 1 4 6 3 6 5 6 6 T T T T T T    0 15 5 17 5 7 4 7 7 F T T F T T    7 0 7 2 5  6 4 6 6 F T T F T T   0  F F F F F F    4 8 8 0 10 6  2 3 4 6 7 F T T T T T   5 13 6 0 3 2 7 4 7 F T T T F T    17 10 7 12 0 3 3 4 3 F T T T F T Allpairs Shortest Path 71 Example We could reinterpret this graph as follows: – Vertices v , v , v , v form a strongly connected subgraph 2 3 6 7 – You can get from any one vertex to any other – With the transitive closure graph, it is much faster finding such strongly connected components 0 6 7 7 8 1 4    0 15 5 17 5    7 0 7 2 5   0    4 8 8 0 10 6   5 13 6 0 3    17 10 7 12 0 Allpairs Shortest Path 72 Summary This topic: – The concept of allpairs shortest paths – The FloydWarshall algorithm – Finding the shortest paths – Finding the transitive closureAllpairs Shortest Path 73 References Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, The MIT Press, 2001, §25.2, pp.62935. Mark A. Weiss, rd Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, 2006, Ch., p.. Joh Kleinberg and Eva Tardos, Algorithm Design, Pearson, 2006. Elliot B. Koffman and Paul A.T. Wolfgang, Objects, Abstractions, Data Structures and Design using C++, Wiley, 2006. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
Presentations
Free
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom