The All-Pairs Shortest Path Problem Example: 1 2 1 8 9 2 3 6
The All-Pairs Shortest Path Problem ◼ Example: 1 2 3 2 8 1 9 6
The A-Pairs Shortest Path Problem Input:An nxn matrix /1...n,1...n such that i is the length of the edge (in a directed graph G=({1,2,..., ),月； ■ Output:A matrix Dwith D[i,]=the distance from ito ■ 1.Dk-6 ■ 2.for k1to n 3. for i1 to n 4. for 1 to n 5. Di,=minDli i,Di,k+ok 6. end for; ■7. end for; ■ 8.end for;
◼ Input: An nn matrix l[1…n, 1…n] such that l[i, j] is the length of the edge (i, j) in a directed graph G=({1, 2, …, n}, E); ◼ Output: A matrix D with D[i, j]=the distance from i to j; ◼ 1. Dl; ◼ 2. for k1 to n ◼ 3. for i1 to n ◼ 4. for j1 to n ◼ 5. D[i, j]=min{D[i, j], D[i, k]+D[k, j]); ◼ 6. end for; ◼ 7. end for; ◼ 8. end for; The All-Pairs Shortest Path Problem