转自：https://blog.csdn.net/zlambert/article/details/65934805
只有四行的算法——Floyd-Warshall 暑期，小可可准备去一些城市旅行。有些城市之间有公路，有些城市则没有，如下图。为了节省经费以及方便计划旅程，小可可希望在出发之前知道任意两个城市之间的最短路径。 上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路径，也就是求任意两个点之间的最短路径。这个问题也被称为“ 多源最短路径”问题。 我们现在需要一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵(二维数组g)来存储。比如1号城市到2号城市的路程为2，则设g[1][2]=2。 2号城市无法到达4号城市，则设g[2][4]的值为∞。 另外，此处约定一个城市自己到自己的路程也是0，例如g[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）的路程g[4][3]原本是12，如果只通过1号城市中转（4->1->3），路径将缩短为11（g[4][1] + g[1][3] = 5 + 6 = 11）。其实1号城市到3号城市也可以从2号城市中转，使得1号城市到3号城市的路径缩短为5（g[1][2] + g[2][3] = 2 + 3 = 5）。所以如果同时经过1号和2号两个城市中转的话，从4号城市到3号城市的路程会进一步缩短为10。通过这个例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。我们把它一般化。 当任意两点之间不允许经过第三个点时，这些城市之间的最短路程就是初始路程，如下： 假如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何呢？只需要判断g[i][1] + g[1][j]是否比g[i][j]小即可。g[i][j]表示的是从i号顶点到j号顶点之间的路程。其中i是1~n循环，j也是1~n循环，代码实现如下： for(i=1; i<=n; i++) for(j=1; j<=n; j++) if( g[i][j] > g[i][1] + g[1][j] ) g[i][j] = g[i][1] + g[1][j]; 在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为： 通过上图我们可以发现：在只通过1号顶点中转的情况下，3号顶点到2号顶点、4号到2号顶点以及4号到3号顶点的路程都变短了。 接下来继续求在只允许1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路径的结果，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短，即判断g[i][2] + g[2][j]是否比g[i][j]要小，代码实现如下： for(i=1; i<=n; i++) //经过1号顶点 for(j=1; j<=n; j++) if( g[i][j] > g[i][1] + g[1][j] ) g[i][j] = g[i][1] + g[1][j]; for(i=1; i<=n; i++) //经过2号顶点 for(j=1; j<=n; j++) if( g[i][j] > g[i][2] + g[2][j] ) g[i][j] = g[i][2] + g[2][j]; 在只允许经过1号顶点和2号顶点的情况下，任意两点之间的最短路程更新为： 通过上图得知，在相比只允许通过1号顶点进行中转的情况下，这里允许通过1和2号顶点进行中转，使得g[1][3]和g[4][3]的路程变得更短了。 同理，继续再只允许1、2和3号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为： 最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为： 整个算法虽然说起来很麻烦，但是代码实现却非常简单，核心代码只有4行： Floyd算法核心代码： for(k=1; k<=n; k++) for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j]; 这段代码的基本思想是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转 …… 允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号顶点的最短路程。其实这是一种“动态规划”的思想。完整的代码如下： #include #include using namespace std; int main(){ int g[100][100], k, i, j, n, m, t1, t2, t3; int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 cin >> n >> m; //n为顶点个数, m为边数 for(i=1; i<=n; i++) //初始化 for(j=1; j<=n; j++) if(i==j) g[i][j]=0; else g[i][j]=inf; for(i=1; i<=m; i++){ //读入边 cin >> t1 >> t2 >> t3; g[t1][t2] = t3; } for(k=1; k<=n; k++) //floyd算法核心语句 for(i=1; i<=n; i++) for(j=1; j<=n; j++) if(g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[i][k] + g[k][j]; for(i=1; i<=n; i++){ //输出 for(j=1; j<=n; j++) printf("d", g[i][j]); cout << endl; } } 对于上面的程序，输入样例数据： 4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 3 12 4 1 5 样例输出 0 2 5 4 9 0 3 4 6 8 0 1 5 7 10 0 有一点需要注意的是：如何表示正无穷。我们通常将正无穷定义为99999999，因为这样即使两个正无穷相加，其和仍然不超过int类型的范围（C++语言int类型可以存储的最大正整数是2147483647）。通过这种方法可以得到任意两个点之间的最短路径。它的时间复杂度为O(N 3)，令人震撼的是只有四行代码，实现起来非常容易。 另外需要注意的是，Floyd算法不能解决带有“ 负权回路”(或者叫“负权环”)的图，因为带有“负权回路”的图没有最短路径。例如下面的图就不存在1号顶点到3号顶点的最短路径，因为1->2->3->1->2->3->……1->2->3这样路径中，每绕一次1->2->3这样的环，最短路径就会减少1，永远找不到最短路径。其实如果一个图中带有“负权回路”，那么这个图则没有最短路径。 小知识： 此算法由Robert W.Floyd(罗伯特·弗洛伊德)于1962年发表在Communications of the ACM上。弗洛伊德这个牛人是朵奇葩，他原本在芝加哥大学读的文学，但是因为当时美国经济不太景气，找工作比较困难，无奈之下到西屋电气公司当了已经计算机操作员，在IBM650机房值夜班，并由此开始了它的计算机生涯。此外他还和J.W.J.Williams(威廉姆斯)于1964年共同发明了著名的 堆排序算法heapsort。在前面已经介绍了堆排序。弗洛伊德在1978年获得了图灵奖。 通过边实现松弛——Dijkstra算法（贪心法） 本节学习指定一个点（源点)到其余各个顶点的最短路径，也叫做“单源最短路径”。例如下图中的1号顶点到2、3、4、5、6号顶点的最短路径。 与Floyd算法一样，这里仍然使用二维数组g来存储顶点之间边的关系，初始值如下： 我们还需要用一个一维数组dis来存储1号顶点到其余各顶点的初始路程，如下： 我们将此时dis数组中的值称为最短路程的“ 估计值”。 既然求1号顶点到其余各个顶点的最短路程，那就先找一个离1号顶点最近的顶点。通过数组dis可知离1号顶点最近的是2号顶点。当选择了2号顶点后，dis[2]的值就已经从“估计值”变成了“确定值”，即1号顶点到2号顶点的最短路程就是当前dis[2]的值。为什么呀？因为目前离1号顶点最近的是2号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得1号顶点到2号顶点的路程进一步缩短了。因为1号顶点到其他顶点的路程肯定没有1号到2号顶点短。 既然选择了2号顶点，接下来再来看2号顶点有哪些出边。有2->3和2->4这两条边。先讨论通过2->3这条边能否让1号到3号顶点的路程变短，也就是说现在来比较dis[3]和dis[2]+g[2][3]的大小。其中dis[3]表示1号顶点到3号顶点的路程，dis[2]表示1号顶点到2号顶点的路程，g[2][3]表示2->3这条边。所以dis[2]+g[2][3]就表示从1号顶点先到2号顶点，再通过2->3这条边，到达3号顶点的路程。 我们发现dis[3]=12，dis[2]+g[2][3]=1+9=10，dis[3]>dis[2]+g[2][3]，因此dis[3]要更新为10。这个过程称为“ 松弛”，1号顶点到3号顶点的路程即dis[3]，通过2->3这条边松弛成功。这便是Dijkstra算法的主要思想：通过“边”来松弛1号顶点到其余各个顶点的路程。 同理，通过2->4（g[2][4]），可以将dis[4]的值从∞松弛为4（dis[4]初始为∞，dis[2]+g[2][4]=1+3=4，dis[4]>dis[2]+g[2][4]，因此dis[4]要更新为4）。 刚才我们对2号顶点所有的出边进行了松弛。松弛完毕后dis数组为： 接下来，继续在剩下的3、4、5和6号顶点中，选出离1号顶点最近的顶点。通过上面更新过的dis数组，当前离1号顶点最近的是4号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对4号顶点的所有出边（4->3, 4->5和4-6）用刚才的方法进行松弛。松弛完毕后dis数组为： 继续在剩下的3、5和6号顶点中，选出离1号顶点最近的顶点。这次选择3号，对3号顶点的所有出边（3->5）进行松弛。松弛完毕之后dis数组为： 继续在剩下的5和6号顶点中，选出离1号顶点最近的顶点。这次选5号顶点。对5号顶点的所有出边（5->4）进行松弛。松弛完毕之后dis数组为： 最后对6号顶点进行松弛。因为6号顶点没有出边，因此不用处理。最终dis数组如下，这便是1号顶点到其余各顶点的最短路径。 现在我们总结下算法的基本思想。 Dijkstra算法的基本思想： 每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。 基本步骤： 1. 将所有顶点分为两部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book数组来记录哪些顶点再集合P中。例如对于某个顶点i，如果book[i]为1则表示这个顶点再集合P中，如果book[i]为0则表示这个顶点再集合Q中。 2. 设置源点s到自己的最短路径为0即 dis[s]=0。若存在有源点能直接到达的顶点i，则把dis[i]设为g[s][i]。同时把所有其他（源点不能直接到达的）顶点的最短路径设为∞。 3. 在集合Q的所有顶点中选择一个离源点s最近的顶点u（即dis[u]最小）加入到集合P。并考察所有以点u为起点的边，对每一条边进行松弛操作。例如存在一条从u到v的边，那么可以通过将u->v添加到尾部来拓展一条从s到v的路径，这条路径的长度时dis[u]+g[u][v]。如果这个值比目前已知的dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。 4. 重复第3步，如果集合Q为空，算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。 c++ code： #include <iostream> using namespace std; int main(){ int g[100][100], dis[100], vis[100]; int i, j, n, m, t1, t2, t3, u, v, min; cin >> n >> m; for (i=1; i<=n; i++) //初始化 for (j=1; j<=n; j++) if (i==j) g[i][j]=0; else g[i][j]=99999999; for (i=1; i<=m; i++){ //读入边 cin >> t1 >> t2 >> t3; g[t1][t2]=t3; } //初始化dis数组，这里是1号顶点到其余各个顶点的初始路径 for(i=1; i<=n; i++) dis[i]=g[1][i]; for(i=1; i<=n; i++) vis[i]=0; vis[1]=1; for(i=1; i<n; i++){ //dijkstra算法核心语句 //找到离1号顶点最近的顶点 min=99999999; for(j=1; j<=n; j++) if(vis[j]==0 && dis[j]<min){ min="dis[j];" u="j;" }="" vis[u]="1;" for(v="1;" v<="n;" v++)="" if(g[u][v]<99999999){="" if(dis[v]="" style="margin: 0px; padding: 0px; outline: 0px;"> dis[u]+g[u][v]) dis[v]=dis[u]+g[u][v]; } } for(i=1; i<=n; i++) cout << dis[i] << " "; return 0; } 可以输入下列数据进行验证。第一行两个整数n和m。n为顶点个数，m为边的条数。接下来m行，每行3个数x,y和z，表示顶点x到顶点y边的权值z。 6 9 1 2 1 1 2 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4 运行结果为： 0 1 8 4 13 17 【例题1】计算从源顶点1到其它顶点间的最短路径 对下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下面的表中。 Dijkstra算法的迭代过程： c++ code： int dist[32767],prev[32767],a[100][100]; void dijkstra(int v0){ bool s[100]; // 判断是否已存入该点到s集合中 int n=100; for(int i=1; i<=n; ++i){ dist[i] = a[v0][i]; s[i] = false; // 初始都未用过该点 if(dist[i] == 32767) rev[i] = -1; else prev[i] = v0; } dist[v0] = 0; s[v0] = true; for(int i=2; i<=n; i++){ int mindist = 32767; int u = v0; //找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if((!S[j]) && dist[j] < mindist){ u = j; // u保存当前邻接点中距离最小的点的号码 mindist = dist[j]; } s[u] = true; for(int j=1; j<=n; j++) if((!S[j]) && a[u][j]<32767){ //在通过新加入的u点路径找到离v0点更短的路径 if(dist[u] + a[u][j] < dist[j]){ dist[j] = dist[u] + a[u][j]; //更新dist prev[j] = u; //记录前驱顶点 } } } } 【程序1】畅通工程 某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。 现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。 输入格式： 第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。 接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。 再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。 输出格式： 输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1。 样例输入1： 3 3 0 1 1 0 2 3 1 2 1 0 2 样例输入2： 3 1 0 1 1 1 2 样例输出1： 2 样例输出2： -1 #include<iostream> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; int n,m,s,t; int map[210][210],dis[210],vis[210]; void Dijkstra(int src){ int i; for(i=0;i<n;i++){ dis[i]=map[src][i]; vis[i]=0; } dis[src]=0; vis[src]=1; int j,k,tmp; for(i=0;i<n;i++){ tmp=INF; for(j=0;j<n;j++) if(!vis[j] && tmp>dis[j]){ k=j; tmp=dis[j]; } if(tmp==INF) break; vis[k]=1; for(j=0;j<n;j++) if(!vis[j] && dis[j]>dis[k]+map[k][j]) dis[j]=dis[k]+map[k][j]; } } int main(){ cin >> n >> m; int u,v,w; for(int i=0;i<n;i++) for(int j=0;j<n;j++) map[i][j]=INF; for(int i=0;i<m;i++){ cin >> u >> v >> w; if(map[u][v]>w) map[u][v]=map[v][u]=w; } cin >> s >> t; Dijkstra(s); if(dis[t]==INF) cout << "-1\n"; else cout << dis[t] << endl; return 0; }