最短路算法(Floyd、Dijkstra)

xiaoxiao2021-02-28  5

转自: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; }
转载请注明原文地址: https://www.6miu.com/read-1600296.html

最新回复(0)