Floyd–Warshall Algorithm [弗洛伊德最短路径算法]
最短路径问题是图论，乃至整个计算机算法领域的一个重要问题，寻找最短路径的方法根据情况不同也会有不同的变化，Floyd算法算是其中比较简单易用的一个。
首先，Floyd解决的是多源最短路径，也就是说算法的结果可以为多个源节点（起始点）提供最短路径结果。其具体思路是不断的加入新的节点然后重新计算每个节点之间的路径，最后加入所有节点后，得到的结果就是任意一个节点到达另一节点的最短路径矩阵。
具体我考虑下面的图，边的数字代表此边的权重，可以简单的理解为该路径的长度。
所以跟根据此图，我们可以得到一个描述点和点之间距离的矩阵（无中转节点），比如e[1][2]是从节点1和节点2的路径。如果两个点没有直接的边相连暂时标注为X，可以解读为无限大
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 2 | 6 | 4 |
| 2 | X | 0 | 3 | X |
| 3 | 7 | X | 0 | 1 |
| 4 | 5 | X | 12 | 0 |
现在考虑节点1作为中转节点的情况，并且重新计算边的距离。从图上可以看出，节点1可以到达节点2，节点3，节点4。所以下面比较e[i][j]和e[i][1] + e[1][j]，遍历全部节点后，可以得出新的距离矩阵：
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 2 | 6 | 4 |
| 2 | X | 0 | 3 | X |
| 3 | 7 | 9 | 0 | 1 |
| 4 | 5 | 7 | 11 | 0 |
现在在已经将节点1作为中转节点的情况下，再考虑依次节点2，3，4直至结束。这样做的意味着，考虑节点1的情况下再考虑节点2，就意味着节点1为中转节点，节点2为中转节点，节点1和2同时为中转节点三种情况。再次更新矩阵，比较e[i][j]和e[i][2]和e[2][j]，因为节点2能到达节点3，所以情况比较简单。需要注意的是e[4][3] = 11, e[4][2] + e[2][3] = 10，此时的e[4][2]已经在上一轮考虑节点1为中转节点的情况下更新为11，所以此时的e[4][2] + e[2][3]，其实是以节点1和2同时为中转节点的路径，后续更新3，4节点也是如此。
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 2 | 5 | 4 |
| 2 | X | 0 | 3 | X |
| 3 | 7 | 9 | 0 | 1 |
| 4 | 5 | 7 | 10 | 0 |
再考虑加入节点3作为中转节点的情况，更新矩阵，
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 2 | 5 | 4 |
| 2 | 10 | 0 | 3 | 4 |
| 3 | 7 | 9 | 0 | 1 |
| 4 | 5 | 7 | 10 | 0 |
再考虑加入节点4作为中转节点的情况，更新矩阵，
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 2 | 5 | 4 |
| 2 | 9 | 0 | 3 | 4 |
| 3 | 6 | 8 | 0 | 1 |
| 4 | 5 | 7 | 10 | 0 |
此时获得的矩阵即为任意两点之间最短距离矩阵。
代码实现也是非常简单，核心代码只需五行即可完成
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];
完整代码：
#include <stdio.h>
int main()
{
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//读入边
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//Floyd-Warshall算法核心语句
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];
//输出最终的结果
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("\n");
}
return 0;
}
因为核心代码有三次嵌套迭代，虽然实现起来比较简单，但是算法复杂度为O(N^3)，基本上在目前追求速度的大环境下，效率不高的算法只有在特地场合下才能发挥作用。
Floyd-Warshell最短路径算法，此算法由Robert W. Floyd（罗伯特·弗洛伊德）于1962年发表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍尔）也独立发表了这个算法。 Robert W．Floyd在1978年获得了图灵奖。
本文部分内容源自互联网，坐在马桶上看算法。