文档介绍：Floyd ’ s Algorithm 1 Floyd ’ s Algorithm All pairs shortest path Floyd ’ s Algorithm 2 All pairs shortest path ? The problem: find the shortest path between every pair of vertices of a graph ? The graph : may contain negative edges but no negative cycles ? A representation : a weight matrix where W(i,j)=0 if i=j. W(i,j)= ? if there is no edge between i and j. W(i,j)= “ weight of edge ”? Note: we have shown principle of optimality applies to shortest path problems Floyd ’ s Algorithm 3 The weight matrix and the graph 12345 10115 29032 304 4203 530 ?????????? v 1v 2v 3v 4v 53224 13 19 35 Floyd ’ s Algorithm 4 The subproblems ? How can we define the shortest distance d i,j in terms of “ smaller ” problems? ? One way is to restrict the paths to only include vertices from a restricted subset. ? Initially, the subset is empty. ? Then, it is incrementally increased until it includes all the vertices. Floyd ’ s Algorithm 5 The subproblems ? Let D (k)[ i,j ]=weight of a shortest path from v i to v j using only vertices from { v 1,v 2,…,v k } as intermediate vertices in the path –D (0)=W –D (n)=D which is the goal matrix ? How do pute D (k ) from D (k -1) ? Floyd ’ s Algorithm 6 The Recursive Definition: Case 1: A shortest path from v i to v j restricted to using only vertices from { v 1,v 2,…,v k } as intermediate vertices does not use v k . Then D (k)[ i,j ]= D (k -1)[ i,j ]. Case 2: A shortest path from v i to v j restricted to using only vertices from { v 1,v 2,…,v k } as intermediate vertices does use v k . Then D (k)[ i,j ]= D (k -1)[ i,k ]+ D (k -1)[k,j ]. V iV jV k Shortest Path using intermediate vertices { V 1 , . . . V k -1 } Shortest path using intermediate vertices {V 1 , . . . V k} Floyd ’ s Algorithm 7 The recursive definition ? Since D (k)[ i,j ]= D (k -1)[ i,j ] or D (k)[ i,j ]= D (k -1)[ i,k ]+ D (k -1)[k,j ]. We conclude: D (k)[ i,j ]= min{ D (k -1)[ i,j ], D (k -1)[ i,k ]