All intermediate vertices in 1,2,...,k-1↑↑p2kp1P:all intermediate vertices in {1,2,... ,k)Figure 2. Path p is a shortest path from vertex i to vertex j,andk is the highest-numbered intermediate vertex of p. Path pl,the portion of path p from vertex i to vertex k,has all intermediatevertices in the set (1,2,.::,k-1.The same holds for path p2 fromvertex k to vertex j
i j p1 k p2 All intermediate vertices in {1,2,.,k-1} P:all intermediate vertices in {1,2,.,k} Figure 2. Path p is a shortest path from vertex i to vertex j,and k is the highest-numbered intermediate vertex of p. Path p1, the portion of path p from vertex i to vertex k,has all intermediate vertices in the set {1,2,.,k-1}.The same holds for path p2 from vertex k to vertex j
A recursive solution to the all-pairs shortest paths problem:Let d.(k) be the weight of a shortest path from vertex i tovertex j with all intermediate vertices in the set (1,2,... ,k}A recursive definition is given byd.(k)=if k=0,Wij+11if k 1.min(d.(k-1),di;k(k-1)+dk;(k-1)The matrix D(n)=(d.(n) gives the final answer-d.(n)-for all i,jV-because all intermediate vertices are in theset (1,2,...,n)
A recursive solution to the all- pairs shortest paths problem: • Let dij(k) be the weight of a shortest path from vertex i to vertex j with all intermediate vertices in the set {1,2,.,k}. A recursive definition is given by • dij(k)= wij if k=0, • min(dij(k-1) ,dik (k-1)+dkj(k-1)) if k 1. • The matrix D(n)=(dij(n)) gives the final answer-dij(n)= for all i,j V-because all intermediate vertices are in the set {1,2,.,n}
Computing the shortest-pathweights bottom up:FLOYD-WARSHALL(W)rows[W]nD(0)Wfor k1 to ndo for i1 to ndo for j1 to nd,(k)min(d.(k-1),dik(k-1)+dk.(k-1)return D(n)
Computing the shortest-path weights bottom up: • FLOYD-WARSHALL(W) • n rows[W] • D(0) W • for k 1 to n • do for i 1 to n • do for j 1 to n • dij(k) min(dij(k-1) ,dik (k-1)+dkj(k-1)) • return D(n)
Example:B· Figure 343815427A6
Example: 1 5 4 3 2 3 4 7 -4 8 1 -5 2 • Figure 3 6
(0)=D(0)=(1)=D(1)=
D(0)= (0)= D(1)= (1)=