最短路径-Floyd算法

1. 问题

给定带权有向图G＝(V, E)，对任意顶点vi,vj∈V（i≠j），求顶点vi到顶点vj的最短路径。

2. 解析

①首先，先将图中的数据放入矩阵中存储。比如1→2的距离是2，则设e[1][2]的值为2，2→4无法完成，则设e[2][4]的值为∞，另约定点到自己的距离为0，即e[1][1]的值为0，以此类推。具体如下：

②假设只允许经过1号点，只需要判断e[i][1]+e[i][j]是否比e[i][j]要短即可，那么任意两点之间的最短路径更新为：

③假设允许经过1号店和2号点，只需要在只允许经过1号点时任意两点的最短路程的结果下，再判断如果经过2号点是否可以使得i→j顶点的路程变短，即判断e[i][2]+e[2][j]是否比e[i][j]要小，那么任意两点之间的最短路程更新为：

④同理，继续在只允许经过1、2和3号点的情况下，任意两点之间的最短路程更新为：

⑤最后允许通过所有顶点的情况下，任意两点之间的最短路程更新为：

3. 设计

for (k = 1; k <= n; k++)        
   for (i = 1; i <= n; i++)            
       for (j = 1; j <= n; j++)                
            if (e[i][j] > e[i][k] + e[k][j])                   
                  e[i][j] = e[i][k] + e[k][j];

4. 源码

https://github.com/Wang-2333/Floyd/blob/master/Floyd/Floyd.cpp