弗洛伊德算法（求每一对顶点间的最短路径）

每一对顶点间的最短路径

求解每一对顶点间的最短路径有两种方法：其一是分别以图中的每个顶点为源点共调用n次迪杰斯特拉算法；其二是采用下面介绍的弗洛伊德算法。这两种算法的时间复杂度均为O(n^3)，但后者形式上较简单。

仍然使用带权的邻接矩阵arcs来表示有向网G,求从顶点vi到vj的最短路径。算法的实现要引入以下辅助的数据结构。
(1)二维数组Path[i][j]:最短路径上顶点vj的前一顶点的序号。
(2)一维数组D[i][j]:记录顶点vi和vj之间的最短路径长度。

弗洛伊德算法[算法步骤]
将vi到vj的最短路径长度初始化，即D[i][j]= Garss[i][j],然后进行n次比较和更新。
①在vi和vj间加入顶点v0,比较(vi,vj)和(vi,v0,vj)的路径长度，取其中较短者作为vi到vj的中间顶点序号不大于0的最短路径。
②在vi和vj间加入顶点v1，得到(vi,…,v1)和(v1,…,vj),其中(vi,…,v1)是vi到v1的且中间顶点的序号不大于0的最短路径，(v1,…,vj)是v1到vj的且中间顶点的序号不大于0的最短路径，这两条路径已在上一步中求出。比较(vi,…,v1,…,vj)与上一步求出的vi到vj的中间顶点序号不大于0的最短路径，取其中较短者作为vi到vj的中间顶点序不大于1的最短路径。
③依次类推，在vi和vj间加人顶点vk，若(vi,…,vk)和(vk,…,vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于 k-1的最短路径， 则将(vi,…,vk,…,vj)和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，经过n次比较后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。

根据上述求解过程，图中的所有顶点对vi到vj间的最短路径长度对应一个n阶方阵D。在上述n+1步中，D的值不断变化，对应一个n阶方阵序列。
n阶方阵序列可定义为：
D^(-1) D^(0), D^(1), ……D^(k), ……D^(n-1)
其中：
D^(-1)[i][j] = G.arcs[i][j];
D^(k)[i][j] = Min{D^{(k-1)[i][j],D}(k-1)[i][k]+D^(k-1)[k][j]}

显然, D^(-1)[i][j] 是从vi到vj的中间顶点的序号不大于1的最短路径的长度; D^(k)[i][j] 是从vi到vj的中间顶点的序号不大于k的最短路径的长度; D^(-1)[i][j] 就是从vi到vj的最短路径的长度。

[算法描述]

void ShortestPath,_Floyd (AMGraph G)
{
     //用Floyd算法求有向网G中各对顶点i和j之间的最短路径
    for(i=0;i <G.vexnum;++i)//各对结点之间初始已知路径及距离
        for(j=0;j <G.vexnum; ++j)
         {
           D[i][j]=G.arcs[i][j];
           if(D[i][j]<MaxInt && i!=j) Path[i][j]=i;//如果i和j之间有弧，则将j的前驱置为i
           else Path[i][j]=-1;//如果i和行之间无弧，则将j的前驱置为-1
          }//for
   for(k=0;k < G. vexnum; ++k)//相当于依次向<vi,vj>中加入顶点v0……v(n-1)
       for(i=0;i <G. vexnum;++i)
           for(j=0;j <G.vexnum;++j)
               if(D[i][k]+D[k][j]<D[i][j])//从i经k到j的一条路径更短
              {
                 D[i][j]=D[i][k]+D[k][j];//更新D[i][j]
                 Path[i][j]=Path[k][j];//更改j的前驱为k
              }//if
}

利用以上算法对如图所示的有向网求解最短路径，给出每一对顶点之间的最短路径及其路径长度长度在求解过程中的变化。

D^(-1)就是其初始化矩阵。

以下的Path是与上边的D是对应的，无穷和零对应的Path均为-1；
如何从表中读取两个顶点之间的最短路径?以 Path^(3) 为例， 对最短路径的读法加以说明。从 D^(3) 知，顶点1到顶点2的最短路径长度为D[1][2]=8，其最短路径看Path[1][2]=3 ,表明顶点2的前驱是顶点3;再看Path[1][3]=1，表明顶点3的前驱是顶点1。所以从顶点 1到顶点2的最短路径为<1,3>，❤️,2>。