坐在马桶上看算法：只有五个元素的弗洛伊德最短路径算法_0

暑假，小恒要去一些城市旅游。有的城市之间有公路，有的城市之间没有公路，如下图。为了省钱和方便出行规划，小衡希望在出发前知道任意两个城市之间的最短距离。上图中4个城市共有8条道路，道路上的数字表示道路的长度。请注意，这些道路是单向的。我们现在需要求任意两个城市之间的最短距离，即求任意两点之间的最短路径。这个问题也被称为“多源最短路径”问题。现在我们需要一个数据结构来存储图的信息，我们还是可以用一个4*4的矩阵（二维数组e）来存储。例如城市1到城市2的距离为2，则将e[1][2]的值设置为2。如果城市2无法到达城市4，则将e[2][4]的值设置为∞.另外，这里规定一个城市对自己是0，比如e[1][1]是0，如下。现在回到问题：如何找到任意两点之间的最短路径？通过前面的学习，我们知道可以通过深度优先或者广度优先搜索找到两点之间的最短路径。因此，通过进行n2次深度或广度优先搜索，即每两点进行一次深度或广度优先搜索，即可得到任意两点之间的最短路径。但是还有别的办法吗？我们想一想，根据我们以往的经验，如果我们想缩短任意两点之间的距离（比如从顶点a到顶点b），只能引入第三个点（顶点k），并通过这个Vertexk中转是a->k->b，可以缩短原来顶点a到顶点b的距离。那么1~n中的哪一点是过境点k呢？有时甚至更短，不仅要经过一个点，还要经过两个或多个点，即a->k1->k2b->或a->k1->k2…->k->i…->b.比如上图中4号城市到3号城市（4->3）的距离e[4][3]原本是12，如果只经过1号城市（4->1->3），距离会缩短为11（e[4][1]+e[1][3]=5+6=11）。其实1号城到3号城也可以通过2号城中转，这样1号城到3号城的距离就缩短为5(e[1][2]+e[2][3]=2+3=5）。那么如果同时中转1号和2号城市，4号城市到3号城市的距离会进一步缩短为10。通过这个例子，我们发现每个顶点都有可能缩短其他两个顶点之间的距离。好的，让我们概括一下这个问题。当任意两点之间不允许有第三个点时，这些城市之间的最短距离就是初始距离，如下。如果只允许通过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(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];}}更新任意两点之间只允许经过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]；//在第二个顶点之后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传递。任意两点之间的最短距离更新为：***Allvertexesareallowedtobeas中转，最终任意两点之间的最短距离为：整个算法过程虽然说起来麻烦，但是代码实现很简单，核心代码只有五行：for(k=1;k<=n;k++)对于（i=1；i<=n；i++）对于（j=1；j<=n；j++）如果（e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];这段代码的基本思想是：一开始只允许通过顶点1，然后只允许通过顶点1和2...允许通过1~n的所有顶点,并找到任意两点之间的最短距离。一句话就是：从第i个顶点到第j个顶点，只经过前k个点的最短距离。其实这是一种“动态规划”思想，我们将在《啊哈！算法2——伟大思维闪耀时》中详细讨论。该算法的完整代码如下：#includeintmain(){inte[10][10],k,i,j,n,m,t1,t2,t3;intinf=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;否则[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");}返回0;需要注意的一件事是如何表示正无穷大。我们通常把正无穷大定义为99999999，因为即使两个正无穷大相加，和仍然不超过int类型的范围（C语言int类型可以存储的最大正整数是2147483647）。在实际应用中，最好预估一下最短路径的上限，只需要设置得比它大一点即可。比如有100条边，如果每条边不超过100，就把正无穷设置为10001就好了。如果你觉得不能把正无穷和其他值相加得到一个大于正无穷的数，我们比较的时候只需要加上两个判断条件，注意下面代码中划线的语句。//Floyd-Warshall算法核心语句for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(e[i][k]e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j]；上面代码的输入数据样式为：481221361442333173414154312***一行中的两个数字是n和m，n代表顶点数，m代表边数。接下来m行，每行有三个数t1，t2，t3，表示顶点t1到顶点t2的距离为t3。最终结果如下：通过这种方法，我们可以找到任意两点之间的最短路径。它的时间复杂度是O(N3)。非常震撼的是，它只有五行代码，而且非常容易实现。正是因为非常容易实现，如果时间复杂度要求不高，用Floyd-Warshall求两个指定点之间的最短路径或者一个点到其他顶点的最短路径也是可行的.当然还有更快的算法，请参阅下一节：Dijkstra算法。另外需要注意的是，Floyd-Warshall算法无法求解带有“负权重循环”（或称“负权重循环”）的图，因为带有“负权重循环”的图没有最短路径。比如下图，就没有顶点1到顶点3的最短路径。因为在1->2->3->1->2->3->…->1->2-的路径中>3，最短路径将减1，永远找不到最短路径。事实上，如果一个图中存在“负权回路”，那么这个图就不存在最短路径。该算法由RobertW.Floyd于1962年在《CommunicationsoftheACM》中发表。同年，史蒂芬·沃歇尔（StephenWarshall）也独立发表了该算法。罗伯特W．弗洛伊德是一个很棒的人。他原本在芝加哥大学学习文学，但由于当时美国经济不景气，很难找到工作。无奈之下，他在西屋电气公司做电脑操作员，在IBM650机房上夜班，并由此开始了他的计算机生涯。此外，他和J.W.J.威廉姆斯（Williams）于1964年共同发明了著名的堆排序算法HEAPSORT。我们将在第7章学习堆排序算法。RobertW．Floyd于1987年获得图灵奖。博客地址：http://ahalei.blog.51cto.com/4767671/1383613