floyd算法求最短路径问题（弗洛伊德算法思想简述）

通常，数组用循环来处理，一般来说，一维数组的数据处理可以使用单重循环或双重循环。如输出数组元素值，从一个数组中挑选最大值或最小值等可以使用单重循环。而对于数组的排序一般使用双重循环，因为单重循环可以挑出一个元素的最大值或最小值，而有n个元素的数组则通过n次挑选便可完成整个数组的排序，所以在单重循环外再嵌套一个循环即可。

对于二维数组的数据处理，通常可以使用双重循环或三重循环，如二维数组元素值的输出，便可以使用双重循环，而矩阵（二维数组）乘法，便可以使用三重循环：

const int maxn=105; int a[maxn][maxn],b[maxn][maxn]; int ans[maxn][maxn]; int a_n,a_m,b_n,b_m; void mul(){ for(int i=0; i<a_m; i++){ // i循环数组a的行for(int j=0; j<b_n; j++){// j循环数组b的列for(int k=0; k<a_n; k++){ // k循环数组a的列，数组b的行，ans[i][j]+=a[i][k]*b[k][j]; }}}

三重循环的另一个经典应用就是Floyd算法求多源最短路径。

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

其算法的核心是在顶点 i 和顶点 j 之间，插入顶点k，看是否能够缩短 i 和 j 之间的距离（松驰操作）。

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

可以画成如下的简图↓

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

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

现在回到问题，如何求任意两点之间最短路径呢？

我们来想一想，从a到b，直接相连（到达）不一定是最短的，如果经过第三个点（顶点k），并通过这个顶点k中转即a->k->b，有可能是从顶点a点到顶点b的最短路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即a→k1→k2→b或者a→k1→k2→…→ki→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循环，代码实现如下↓

在只允许经过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和2号顶点的情况下，任意两点之间的最短路程更新为：

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

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

最后允许通过所有顶点作为中转（在双重循环外再嵌套一个循环），任意两点之间最终的最短路程为：

整个算法过程虽然说起来很麻烦，但是代码实现却非常简单，核心代码就是一个三重循环：

这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。其实这是一种“动态规划”的思想。

Floyd算法可以求出任意两个点之间最短路径。它的时间复杂度是O(n?)，空间复杂度是O(n?)。令人很震撼的是它竟然只有五行代码，实现起来非常容易。

Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行V(V为顶点数)次Dijkstra算法，也要高于执行V次SPFA算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。

缺点：时间复杂度比较高，不适合计算大量数据。

如果需要求出各点之间最短路径所经过的节点，只需增加一个前驱数组即可。如p[i][j]，当点p[i][j]经过k点能取得更短路径时，令

p[i][j]=p[k][j]; // 更改j的前驱为k

如点4至点3的最短距离为：10，路线:4 1 2 3，是怎样求出来的呢？程序运行完后，由数组p[i][j]即可得出此路径（参照最后源代码和最后运行结果）：

p[4][3]＝2 p[4][2]＝1 p[4][1]＝4  // i=p[i][j]时结束路径搜索

因为是按顺序求出的前驱，所以颠倒一下顺序（使用栈）即可。

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

Robert W.Floyd(1936-2001)↓

Stephen Warshall (1935–2006)↓

迪杰斯特拉dijkstra算法是一个单源最短路径的算法，即只能求得一个顶点到其它各顶点之间的最短路径。如果我们每次以一个顶点为源点，重复执行dijkstra算法n次，这样便可以求得每一顶点之间的最短路径。关于dijkstra算法，详细内容可由下面链接去了解。

迪杰斯特拉dijkstra算法：一个既贪心又最优的图的最短路径算法

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

附源代码：

#include <stdio.h>#include <stdlib.h>#include <stack>usingnamespacestd;#define N 10#define inf 99999999inte[N][N];//顶点数组intp[N][N];//前驱数组voidoutput2Darr(intarr[N][N],intn){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){printf("%10d",arr[i][j]);}printf("\n");}}voidoutputRoute(inti,intj){stack<int>st;printf("点%d至点%d的最短距离为：%d，路线:",i,j,e[i][j]);st.push(j);while(p[i][j]!=i){st.push(p[i][j]);j=p[i][j];}st.push(i);do{printf("%d",st.top()); st.pop(); }while(!st.empty()); printf("\n");}intmain(){intk,i,j,n,m,a,b,s;printf("读入顶点个数n，边的条数m:\n");scanf("%d%d",&n,&m);//初始化for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)e[i][j]=0;elsee[i][j]=inf;printf("读入边,顶点a的编号顶点b的编号两个顶点的距离s,如122;\n");for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&s);e[a][b]=s;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(e[i][j]>0&&e[i][j]<inf)p[i][j]=i;elsep[i][j]=-1;printf("初始矩阵e为：\n");output2Darr(e,n);//Floyd-Warshall算法核心语句for(k=1;k<=n;k++)//插点，kfor(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];p[i][j]=p[k][j];//更改j的前驱为k}printf("全部顶点之间的最短路径为:\n");output2Darr(e,n);printf("各点的前驱为:\n");output2Darr(p,n);outputRoute(4,3);outputRoute(3,2);system("pause");return0;}/*输入（可复制）481221361442333173414154312*//*输出读入顶点个数n，边的条数m:48读入边,顶点a的编号顶点b的编号两个顶点的距离s,如122;1221361442333173414154312初始矩阵e为：026499999999039999999979999999901599999999120全部顶点之间的最短路径为:02549034680157100各点的前驱为:-11214-12341-13412-1点4至点3的最短距离为：10，路线:4123点3至点2的最短距离为：8，路线:3412*/