最短路径--弗洛伊德(Floyd)算法.ppt

0 1 2 3 0 1 2 3 0 1 2 4 0 0 9 2 3 5 0 8 0 1 6 0 8 8 8 8 A(-1) = 4 7 A(0) = 10 3 6 A(1) = D(2) = 12 9 10 D(3) = V2 V3 V0 V1 1 2 3 4 5 6 8 9 以D(2)为基础，以V3为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始通过V0,V1, V2,V3到达Vj的最短路径 。 D(3) [i][j] = min{D(2) [i][j], D(2) [i][3]+D(2) [3][j]} 9 11 8 V3 V2 V0 V1 D(3) [i][j] 即为从Vi到Vj的最短路径长度. * A C B 2 6 4 3 11 0 4 11 6 0 2 3 ? 0 初始： 路径： AB AC BA BC CA 0 4 6 6 0 2 3 7 0 加入B： 路径： AB ABC BA BC CA CAB 0 4 11 6 0 2 3 7 0 加入A： 路径： AB AC BA BC CA CAB 0 4 6 5 0 2 3 7 0 加入C： 路径： AB ABC BCA BC CA CAB 例题： * 例 A C B 2 6 4 3 11 初始： 0 4 11 6 0 2 3 ? 0 length= 0 1 1 2 0 2 3 0 0 path= 加入A： 0 4 11 6 0 2 3 7 0 length= 0 1 1 2 0 2 3 1 0 path= 加入B： 0 4 6 6 0 2 3 7 0 length= 0 1 2 2 0 2 3 1 0 path= 加入C： 0 4 6 5 0 2 3 7 0 length= 0 1 2 3 0 2 3 1 0 path= * 4. 论点：A(-1) [i][j]是从顶点vi 到vj , 中间顶点是 v1的最短路径的长度,A(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)[i][j]是从顶点vi 到vj 的最短路径长度。 证明：归纳证明，始归纳于s (上角标); (1) 归纳基础：当s=-1 时， A(-1) [i][j]= Edge[i][j], vi 到vj , 不经过任何顶点的边，是最短路径。 (2)归纳假设：当sk时， A(s) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于s的最短路径的长度; (3)当s=k时， * i j k A(k-1) [i][k] A(k-1) [k][j] A(k-1) [i][j] 因为：A(k) [i][j] = min { A(k-1)[i][j]， A(k-1)[i][k] + A(k-1)[k][j] } 由归纳假设知： A(k-1)[i][j] :是i到j的最短路径(标号不高于k-1)； A(k-1)[i][k] :是i到k的最短路径(标号不高于k-1)； A(k-1)[k][j] :是k到j的最短路径(标号不高于k-1)； 所以： A(k) [i][j] 是i到j的最短路径(标号不高于k)。 * * 1.问题的提出：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi ? vj，要求求出vi 与vj之间的最短路径和最短路径长度。 2.解决办法 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n3) 方法二：弗洛伊德(Floyd)算法 * 求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧Vi,Vj，则对应元素为权值；否则为? 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕