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

从图的带权邻接矩阵G.arcs出发，假设求顶点Vi到Vj的最短路径。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为G.arcs[i][j]的路径，但该路径是否一定是最短路径，还需要进行n次试探。 2. 第二次，再加一个顶点V1，如果(Vi, … , V1） 和(V1, … , Vj）分别是当前找到的中间顶点序号不大于0的最短路径，那么(Vi, … , V1, … , Vj ）就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj之间顶点序号不大于0的最短路径相比较，取较短者为从Vi到Vj的中间顶点序号不大于1的最短路径。 3. 第三次，再加一个顶点V2，继续进行试探。 V2 V3 V0 V1 1 2 3 4 5 6 8 9 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 D(-1) = D(-1)为有向网的邻接矩阵 第一步:以D(-1)为基础，以V0为中间顶点，求从Vi到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为(Vi,V0)+(V0,Vj) 。 D(0) [i][j] = min{D(-1) [i][j], D(-1) [i][0]+D(-1) [0][j]} 4 7 D(0) = D(0) [i][j] 为从Vi到Vj的中间顶点序号不大于0的最短路径长度. V0 V2 V3 V0 V1 1 2 3 4 5 6 8 9 以D(0)为基础，以V1为中间顶点，求从Vi,到Vj的最短路径。该路径或者为从Vi到Vj的边, 或者为从Vi开始通过V0或V1到达Vj的最短路径 。 D(1) [i][j] = min{D(0) [i][j], D(0) [i][1]+D(0) [1][j]} 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 D(0) = 10 3 6 D(1) = V0 V1 V0 V1 V2 V3 V0 V1 1 2 3 4 5 6 8 9 以D(1)为基础，以V2为中间顶点，求从Vi,到Vj的最短路径。或者为从Vi到Vj的边, 或者为从Vi开始通过V0,V1, V2到达Vj的最短路径 。 D(2) [i][j] = min{D(1) [i][j], D(1) [i][2]+D(1) [2][j]} 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 D(1) = D(2) = 12 9 10 V0 V1 V2 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 CA