算法12 最短路径 弗洛伊德(floyd)算法.ppt

从图的带权邻接矩阵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的最短路径将