多源最短路径算法---Floyd-Warshall

墨蓝 2022-04-23 10:04 358阅读 0赞

![20160821123156145][]

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

![20160821123204567][]

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

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

![20160821123208905][]

现在回到问题：如何求任意两点之间最短路径呢？通过之前的学习我们知道通过深度或广度优先搜索可以求出两点之间的最短路径。所以进行n2遍深度或广度优先搜索，即对每两个点都进行一次深度或广度优先搜索，便可以求得任意两点之间的最短路径。可是还有没有别的方法呢？

我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即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。通过这个的例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。好，下面我们将这个问题一般化。

当任意两点之间不允许经过第三个点时，这些城市之间最短路程就是初始路程，如下。

![20160821123213832][]

如现在只允许经过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循环，代码实现如下。

1.  for(i=1;i<=n;i++)
2.  \{
3.  for(j=1;j<=n;j++)
4.  \{
5.  if ( e\[i\]\[j\] > e\[i\]\[1\]+e\[1\]\[j\] )
6.  e\[i\]\[j\] = e\[i\]\[1\]+e\[1\]\[j\];
7.  \}
8.  \}

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

![20160821123221801][]

通过上图我们发现：在只通过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.  //经过1号顶点
2.  for(i=1;i<=n;i++)
3.  for(j=1;j<=n;j++)
4.  if (e\[i\]\[j\] > e\[i\]\[1\]+e\[1\]\[j\]) e\[i\]\[j\]=e\[i\]\[1\]+e\[1\]\[j\];
5.  //经过2号顶点
6.  for(i=1;i<=n;i++)
7.  for(j=1;j<=n;j++)
8.  if (e\[i\]\[j\] > e\[i\]\[2\]+e\[2\]\[j\]) e\[i\]\[j\]=e\[i\]\[2\]+e\[2\]\[j\];

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

![20160821123227755][]

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

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

![20160821123233786][]

整个算法过程虽然说起来很麻烦，但是代码实现却非常简单，核心代码只有五行：

1.  for(k=1;k<=n;k++)
2.  for(i=1;i<=n;i++)
3.  for(j=1;j<=n;j++)
4.  if(e\[i\]\[j\]>e\[i\]\[k\]+e\[k\]\[j\])
5.  e\[i\]\[j\]=e\[i\]\[k\]+e\[k\]\[j\];

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。其实这是一种“动态规划”的思想，关于这个思想我们将在[《啊哈！算法2——伟大思维闪耀时》][2]在做详细的讨论。下面给出这个算法的完整代码：

1.  \#include <stdio.h>
2.  int main()
3.  \{
4.  int e\[10\]\[10\],k,i,j,n,m,t1,t2,t3;
5.  int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
6.  //读入n和m，n表示顶点个数，m表示边的条数
7.  scanf("%d %d",&n,&m);
8.  
9.  //初始化
10. for(i=1;i<=n;i++)
11. for(j=1;j<=n;j++)
12. if(i==j) e\[i\]\[j\]=0;
13. else e\[i\]\[j\]=inf;
14. //读入边
15. for(i=1;i<=m;i++)
16. \{
17. scanf("%d %d %d",&t1,&t2,&t3);
18. e\[t1\]\[t2\]=t3;
19. \}
20. 
21. //Floyd-Warshall算法核心语句
22. for(k=1;k<=n;k++)
23. for(i=1;i<=n;i++)
24. for(j=1;j<=n;j++)
25. if(e\[i\]\[j\]>e\[i\]\[k\]+e\[k\]\[j\] )
26. e\[i\]\[j\]=e\[i\]\[k\]+e\[k\]\[j\];
27. 
28. //输出最终的结果
29. for(i=1;i<=n;i++)
30. \{
31. for(j=1;j<=n;j++)
32. \{
33. printf("%10d",e\[i\]\[j\]);
34. \}
35. printf("\\n");
36. \}
37. 
38. return 0;
39. \}

有一点需要注意的是：如何表示正无穷。我们通常将正无穷定义为99999999，因为这样即使两个正无穷相加，其和仍然不超过int类型的范围（C语言int类型可以存储的最大正整数是2147483647）。在实际应用中最好估计一下最短路径的上限，只需要设置比它大一点既可以。例如有100条边，每条边不超过100的话，只需将正无穷设置为10001即可。如果你认为正无穷和其它值相加得到一个大于正无穷的数是不被允许的话，我们只需在比较的时候加两个判断条件就可以了，请注意下面代码中带有下划线的语句。

1.  //Floyd-Warshall算法核心语句
2.  for(k=1;k<=n;k++)
3.  for(i=1;i<=n;i++)
4.  for(j=1;j<=n;j++)
5.  if(e\[i\]\[k\]<inf && e\[k\]\[j\]<inf && e\[i\]\[j\]>e\[i\]\[k\]+e\[k\]\[j\])
6.  e\[i\]\[j\]=e\[i\]\[k\]+e\[k\]\[j\];

上面代码的输入数据样式为：

1.  4 8
2.  1 2 2
3.  1 3 6
4.  1 4 4
5.  2 3 3
6.  3 1 7
7.  3 4 1
8.  4 1 5
9.  4 3 12

第一行两个数为n和m，n表示顶点个数，m表示边的条数。

接下来m行，每一行有三个数t1、t2 和t3，表示顶点t1到顶点t2的路程是t3。

得到最终结果如下：

![20160821123239061][]

通过这种方法我们可以求出任意两个点之间最短路径。它的时间复杂度是O(N3)。令人很震撼的是它竟然只有五行代码，实现起来非常容易。正是因为它实现起来非常容易，如果时间复杂度要求不高，使用Floyd-Warshall来求指定两点之间的最短路或者指定一个点到其余各个顶点的最短路径也是可行的。当然也有更快的算法，请看下一节：Dijkstra算法。

另外需要注意的是：Floyd-Warshall算法不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->…->1->2->3这样路径中，每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。其实如果一个图中带有“负权回路”那么这个图则没有最短路。

![20160821123245833][]

此算法由Robert W. Floyd（罗伯特·弗洛伊德）于1962年发表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍尔）也独立发表了这个算法。Robert W．Floyd这个牛人是朵奇葩，他原本在[芝加哥大学][Link 1]读的文学，但是因为当时美国经济不太景气，找工作比较困难，无奈之下到[西屋电气公司][Link 2]当了一名计算机操作员，在IBM650机房值夜班，并由此开始了他的计算机生涯。此外他还和J.W.J. Williams（威廉姆斯）于1964年共同发明了著名的堆排序算法HEAPSORT。堆排序算法我们将在第七章学习。Robert W．Floyd在1987年获得了图灵奖

[20160821123156145]: /images/20220321/582dce5f179c4097b2cbeca45535d29c.png
[20160821123204567]: /images/20220321/2c7af10fb5b14026baf919365eaab1b2.png
[20160821123208905]: /images/20220321/98e47496feb146c68de7066e213d0977.png
[20160821123213832]: /images/20220321/9e6ad0be625243779e6f54062c9528c9.png
[20160821123221801]: /images/20220321/ea6610cf9f5e49b7996c4638de49188a.png
[20160821123227755]: /images/20220321/92067f12caed4567ba396b9de22eee64.png
[20160821123233786]: /images/20220321/d5a28b1591b54a0cac9fd60eab093070.png
[2]: https://www.baidu.com/s?wd=%E3%80%8A%E5%95%8A%E5%93%88%EF%BC%81%E7%AE%97%E6%B3%952%E2%80%94%E2%80%94%E4%BC%9F%E5%A4%A7%E6%80%9D%E7%BB%B4%E9%97%AA%E8%80%80%E6%97%B6%E3%80%8B&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[20160821123239061]: /images/20220321/ca7512ad04c7429aac5397d046a011b6.png
[20160821123245833]: /images/20220321/638feb9f10a14353bf5199d9f0505301.png
[Link 1]: https://www.baidu.com/s?wd=%E8%8A%9D%E5%8A%A0%E5%93%A5%E5%A4%A7%E5%AD%A6&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[Link 2]: https://www.baidu.com/s?wd=%E8%A5%BF%E5%B1%8B%E7%94%B5%E6%B0%94%E5%85%AC%E5%8F%B8&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd