只有五行的Floyd最短路径算法

暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。

上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。

现在需要一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵（二维数组e）来存储。比如1号城市到2号城市的路程为2，则设e[1][2]的值为2。2号城市无法到达4号城市，则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0，例如e[1][1]为0，具体如下。

如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何求呢？只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1~n循环，j也是1~n循环，代码实现如下。

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]; 

在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为：

通过上图我们发现：在只通过1号顶点中转的情况下，3号顶点到2号顶点（e[3][2]）、4号顶点到2号顶点（e[4][2]）以及4号顶点到3号顶点（e[4][3]）的路程都变短了。

接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。

//经过1号顶点   
for(i=1;i<=n;i++)   
    for(j=1;j<=n;j++)   
 if (e[i][j] > e[i][1]+e[1][j])  e[i][j]=e[i][1]+e[1][j];   
//经过2号顶点   
for(i=1;i<=n;i++)   
    for(j=1;j<=n;j++)   
 if (e[i][j] > e[i][2]+e[2][j])  e[i][j]=e[i][2]+e[2][j]; 

在只允许经过1和2号顶点的情况下，任意两点之间的最短路程更新为

通过上图得知，在相比只允许通过1号顶点进行中转的情况下，这里允许通过1和2号顶点进行中转，使得e[1][3]和e[4][3]的路程变得更短了。

同理，继续在只允许经过1、2和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];