最短路径算法:算法|有趣实用的“最短路径”问

 2021-06-29 15:58    77  

有一天,孩子回来对我说:“妈妈,听说马尔代夫很不错,放假了我想去玩最短路径算法。”马尔代夫?我也想去!没有人不向往一场说走就走的旅行!“其实我想去的地方很多,呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是我们拿出地图,标出想去的地点,然后计算最短路线,估算大约所需的时间,有了这张秘制地图,一场说走就走的旅行不是梦!

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

“哇最短路径算法,感觉我们像凡尔纳的《环游地球八十天》,好激动!可是老妈你也太out了,学计算机的最短路线你用手算?”

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

暴汗……最短路径算法,“小子你别牛,你知道怎么算?”

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

“呃,好像是叫什么迪杰斯特拉的人会算。”

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

哈哈,关键时刻还要老妈上场了!

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

1 问题分析根据题目描述可知,这是一个求单源最短路径的问题。给定有向带权图G =(V,E),其中每条边的权是非负实数。此外,给定V中的一个顶点,称为源点。现在要计算从源到所有其他各顶点的最短路径长度,这里路径长度指路上各边的权之和。

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

如何求源点到其他各点的最短路径呢?

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

如图9所示,迪杰斯特拉(Edsger Wybe Dijkstra),荷兰人,计算机科学家。他早年钻研物理及数学,后转而研究计算学。他曾在1972年获得过素有“计算机科学界的诺贝尔奖”之称的图灵奖,与Donald Ervin Knuth并称为我们这个时代最伟大的计算机科学家。

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

2 算法设计Dijkstra 算法是解决单源最短路径问题的贪心算法,它先求出长度最短的一条路径,再参照该最短路径求出长度次短的一条路径,直到求出从源点到其他各个顶点的最短路径。

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

Dijkstra算法的基本思想是首先假定源点为u,顶点集合V被划分为两部分:集合S和 V-S。初始时 S 中仅含有源点 u,其中 S 中的顶点到源点的最短路径已经确定。集合V-S中所包含的顶点到源点的最短路径的长度待定,称从源点出发只经过S中的点到达V-S中的点的路径为特殊路径,并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度。

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

Dijkstra算法采用的贪心策略是选择特殊路径长度最短的路径,将其连接的V-S中的顶点加入到集合S中,同时更新数组dist[]。一旦S包含了所有顶点,dist[]就是从源到所有其他顶点之间的最短路径长度。

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

① 数据结构

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

设置地图的带权邻接矩阵为map[][],即如果从源点 u 到顶点 i 有边,就令 map[u][i] 等于 (u,i) 的权值,否则 map[u][i]=∞(无穷大);采用一维数组 dist[i]来记录从源点 u 到 i 顶点的最短路径长度;采用一维数组p[i]来记录最短路径上 i 顶点的前驱。

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

② 初始化

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

令集合S={u},对于集合V-S中的所有顶点x,初始化dist[i]=map[u][i],如果源点u到顶点i有边相连,初始化p[i]=u,否则p[i]= -1。

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

③ 找最小

最短路径算法:算法|有趣实用的“最短路径”问题:最简单通透的图解(C++)

在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点 t,即dist[t]=min(dist[j] | j属于V-S集合),则顶点 t 就是集合V-S中距离源点 u 最近的顶点。

④ 加入S战队

将顶点 t 加入集合S中,同时更新V-S。

⑤ 判断是否计算结束

如果集合V-S为空,算法结束,否则转⑥。

⑥ 借东风

在③中已经找到了源点到 t 的最短路径,那么对集合V-S中所有与顶点 t 相邻的顶点 j,都可以借助 t 走捷径。如果dist[j]>dist[t]+map[t][j],则dist[j]=dist[t]+map[t][j],记录顶点 j 的前驱为 t,有p[j]= t,转③。

由此,可求得从源点 u 到图G的其余各个顶点的最短路径及长度,也可通过数组 p[] 逆向找到最短路径上经过的城市。

3 完美图解现在我们有一个景点地图,如图10所示↓,假设从1号结点出发,求到其他各个结点的最短路径。

算法步骤如下。

3.1 数据结构

设置地图的带权邻接矩阵为map[][],即如果从顶点 i 到顶点 j 有边,则map[i][j]等于(i,j)的权值,否则map[i][j]=∞(无穷大),如图11所示↑。

3.2 初始化

令集合S={1},V-S={2,3,4,5},对于集合V-S中的所有顶点 x,初始化最短距离数组dist[i]=map[1][i],dist[u]=0,如图12所示↓。如果源点1到顶点i有边相连,初始化前驱数组p[i]=1,否则p[i]= -1,如图13所示↓。

3.3 找最小

在集合V-S={2,3,4,5}中,依照贪心策略来寻找V-S集合中 dist[] 最小的顶点 t,如图14所示。

找到最小值为2,对应的结点 t=2。

3.4 加入S战队

将顶点t=2加入集合S中S={1,2},同时更新V-S={3,4,5},如图15所示。

3.5 借东风

刚刚找到了源点到 t=2 的最短路径,那么对集合V-S中所有 t 的邻接点 j,都可以借助 t 走捷径。我们从图或邻接矩阵都可以看出,2号结点的邻接点是 3 和 4 号结点,如图16所示↑。

先看3号结点能否借助2号走捷径:dist[2]+map[2][3]=2+2=4,而当前dist[3]=5>4,因此可以走捷径即2→3,更新dist[3]=4,记录顶点3的前驱为2,即p[3]= 2。

再看4号结点能否借助2号走捷径:如果dist[2]+map[2][4]=2+6=8,而当前dist[4]=∞>8,因此可以走捷径即2→4,更新dist[4]=8,记录顶点4的前驱为2,即p[4]= 2。

更新后如图17和图18所示。

3.6 找最小

在集合V-S={3,4,5}中,依照贪心策略来寻找dist[]具有最小值的顶点t,依照贪心策略来寻找V-S集合中dist[]最小的顶点t,如图19所示。

找到最小值为4,对应的结点t=3。

3.7 加入S战队

将顶点t=3加入集合S中S={1,2,3},同时更新V-S={4,5},如图20所示↑。

3.8 借东风

刚刚找到了源点到t =3的最短路径,那么对集合V-S中所有 t 的邻接点 j,都可以借助 t 走捷径。我们从图或邻接矩阵可以看出,3号结点的邻接点是4和5号结点。

先看4号结点能否借助3号走捷径:dist[3]+map[3][4]=4+7=11,而当前dist[4]=8<11,比当前路径还长,因此不更新。

再看5号结点能否借助3号走捷径:dist[3]+map[3][5]=4+1=5,而当前dist[5]=∞>5,因此可以走捷径即3—5,更新dist[5]=5,记录顶点5的前驱为3,即p[5]=3。

更新后如图21和图22所示。

3.9 找最小

在集合V-S={4,5}中,依照贪心策略来寻找V-S集合中dist[]最小的顶点t,如图23所示。

找到最小值为5,对应的结点t=5。

3.10 加入S战队

将顶点t=5加入集合S中S={1,2,3,5},同时更新V-S={4},如图24所示↑。

3.11 借东风

刚刚找到了源点到t =5的最短路径,那么对集合V-S中所有t的邻接点j,都可以借助t走捷径。我们从图或邻接矩阵可以看出,5号结点没有邻接点,因此不更新,如图25和图26所示。

3.12 找最小

在集合V-S={4}中,依照贪心策略来寻找dist[]最小的顶点 t,只有一个顶点,所以很容易找到,如图27所示。

找到最小值为8,对应的结点t=4。

3.13 加入S战队

将顶点t加入集合S中S={1,2,3,5,4},同时更新V-S={ },如图28所示↑。

3.14 算法结束

V-S={ }为空时,算法停止。

(上述的重复过程可以借助循环迭代完成)

由此,可求得从源点u到图G的其余各个顶点的最短路径及长度,也可通过前驱数组p[]逆向找到最短路径上经过的城市,如图29所示。

例如,p[5]=3,即5的前驱是3;p[3]=2,即3的前驱是2;p[2]=1,即2的前驱是1;p[1]= -1,1没有前驱,那么从源点1到5的最短路径为1→2→3→5。

4 伪代码详解4.1 数据结构

n:城市顶点个数。

m:城市间路线的条数。

map[][]:地图对应的带权邻接矩阵。

dist[]:记录源点 u 到某顶点的最短路径长度。

p[]:记录源点到某顶点的最短路径上的该顶点的前一个顶点(前驱)。

flag[]:flag[i]等于true,说明顶点i已经加入到集合S,否则顶点i属于集合V-S。const int N = 100; //初始化城市的个数,可修改const int INF = 1e7; //无穷大int map[N][N],dist[N],p[N],n,m;bool flag[N];4.2 初始化源点 u 到其他各个顶点的最短路径长度,初始化源点 u 出边邻接点(t 的出边相关联的顶点)的前驱为 u:

bool flag[n]; //如果flag[i]等于true,说明顶点 i已经加入到集合S;否则 i 属于集合V-Sfor(int i = 1; i <= n; i ++){……dist[i] = map[u][i]; //初始化源点u到其他各个顶点的最短路径长度……flag[i]=false;……if(dist[i]==INF)…………p[i]=-1; //说明源点u到顶点i无边相连,设置p[i]=-1……else…………p[i]=u; //说明源点u到顶点i有边相连,设置p[i]=u}4.3 初始化集合S,令集合S={u},从源点到 u 的最短路径为0。

flag[u]=true; //初始化集合S中,只有一个元素:源点 udist[u] = 0; //初始化源点 u的最短路径为0,自己到自己的最短路径4.4 找最小

在集合V-S中寻找距离源点 u 最近的顶点 t,若找不到 t,则跳出循环;否则,将 t 加入集合S。

int temp = INF,t = u ;for(int j = 1 ; j <= n ; j ++) //在集合V-S中寻找距离源点u最近的顶点t……if( !flag[j] && dist[j] < temp)……{…………t=j; //记录距离源点u最近的顶点…………temp=dist[j];……}if(t == u) return ; //找不到t,跳出循环flag[t] = true; //否则,将t加入集合S4.5 借东风

考查集合V-S中源点 u 到 t 的邻接点 j 的距离,如果源点 u 经过 t 到达 j 的路径更短,则更新dist[j] =dist[t]+map[t][j],即松弛操作,并记录 j 的前驱为 t:

for(int j = 1; j <= n; j ++) //更新集合V-S中与t邻接的顶点到源点u的距离……if(!flag[j] && map[t][j]<INF) //!flag[j]表示j在V-S中,map[t][j]<INF表示t与j邻接…………if(dist[j]>(dist[t]+map[t][j])) //经过t到达j的路径更短…………{………………dist[j]=dist[t]+map[t][j] ;………………p[j]=t; //记录j的前驱为t……}重复4.4~4.5,直到源点 u 到所有顶点的最短路径被找到。

5 CPP代码5.1 代码

5.2 运行后输入

有如下城市路线图:

请输入城市的个数:5请输入城市之间的路线的个数:11请输入城市之间的路线以及距离(可复制粘贴):1 5 125 1 81 2 162 1 295 2 322 4 134 2 271 3 153 1 213 4 74 3 19请输入小明所在的位置:55.3 运行后输出

6 算法解析及优化拓展6.1 算法复杂度

6.1.1 时间复杂度

在Dijkstra算法描述中,一共有4个for语句,第①个for语句的执行次数为n,第②个for语句里面嵌套了两个for语句③、④,它们的执行次数均为n,对算法的运行时间贡献最大,当外层循环标号为1时,③、④语句在内层循环的控制下均执行n次,外层循环②从1~n。因此,该语句的执行次数为n*n= n2,算法的时间复杂度为O(n2)。

6.1.2 空间复杂度:由以上算法可以得出,实现该算法所需要的辅助空间包含为数组flag、变量i、j、t和temp所分配的空间,因此,空间复杂度为O(n)。

6.2 算法优化拓展

在for语句③中,即在集合V-S中寻找距离源点u最近的顶点 t,其时间复杂度为O(n),如果我们使用优先队列,则可以把时间复杂度降为O(log n)。那么如何使用优先队列呢?

6.2.1 优先队列

普通的队列是一种先进先出的数据结构,元素在队列尾部追加,而从队列头部删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。

优先队列具有最高级先出的行为特征。优先队列是0个或多个元素的集合,每个元素都有一个优先权值。

6.2.2 数据结构

在上面的例子中,我们使用了一维数组dist[t]来记录源点 u 到顶点 t 的最短路径长度。在此为了操作方便,我们使用结构体的形式来实现,定义一个结构体Node,里面包含两个成员:u为顶点,step为源点到顶点u的最短路径。

struct Node{……int u,step; // u为顶点,step为源点到顶点u的最短路径……Node(){};……Node(int a,int sp){…………u = a; //参数传递,u为顶点…………step = sp; //参数传递,step为源点到顶点u的最短路径……}……bool operator < (const Node& a)const{…………return step > a.step; //重载 <,step(源点到顶点u的最短路径)最小值优先……}};上面的结构体中除了两个成员变量外,还有一个构造函数和运算符优先级重载,下面详细介绍其含义用途。

为什么要使用构造函数?

如果不使用构造函数也是可以的,只定义一般的结构体,里面包含两个参数:

struct Node{……int u,step; // u为顶点,step为源点到顶点u的最短路径};那么在变量参数赋值时,需要这样赋值:

Node vs ; //先定义一个Node结点类型变量vs.u =3 ,vs.step = 5; //分别对该变量的两个成员进行赋值采用构造函数的形式定义结构体:

struct Node{……int u,step;……Node(){};……Node(int a,int sp){…………u = a; //参数传递u为顶点…………step = sp; //参数传递step为源点到顶点u的最短路径……}};则变量参数赋值就可以直接通过参数传递:

Node vs(3,5)上面语句等价于:vs.v =3 ,vs.step = 5;很明显通过构造函数的形式定义结构体,参数赋值更方便快捷,后面程序中会将结点压入优先队列:

priority_queue <Node> Q; // 创建优先队列,最小值优先Q.push(Node(i,dist[i])); //将结点Node压入优先队列Q//参数i传递给顶点u, dist[i]传递给step6.2.3 使用优先队列优化的Dijkstra算法源代码:

6.2.4 运行后输入

参考前面提到的城市路线图:

请输入城市的个数:5请输入城市之间的路线的个数:8请输入城市之间u,v的路线以及距离w(可复制粘贴):1 2 21 3 52 3 22 4 63 4 73 5 14 3 24 5 5请输入小明所在的位置:16.2.5 运行后输出

小明所在的位置:1小明:1--->要去的位置:1 最短距离为:0小明:1--->要去的位置:2 最短距离为:2小明:1--->要去的位置:3 最短距离为:4小明:1--->要去的位置:4 最短距离为:8小明:1--->要去的位置:5 最短距离为:5在使用优先队列的 Dijkstra 算法描述中,while (!Q.empty())语句执行的次数为n,因为要弹出n个最小值队列才会空;Q.pop()语句的时间复杂度为logn,while语句中的for语句执行n次,for语句中的Q.push (Node(i,dist[i]))时间复杂度为logn。因此,总的语句的执行次数为n* logn+n²*logn,算法的时间复杂度为O(n²logn)。

貌似时间复杂度又变大了?

这是因为我们采用的邻接矩阵存储的,如果采用邻接表存储,那么for语句④松弛操作就不用每次执行n次,而是执行 t 结点的邻接边数x,每个结点的邻接边加起来为边数E,那么总的时间复杂度为O(n*logn+E*logn),如果E>=n,则时间复杂度为O(E*logn)。

注意:优先队列中尽管有重复的结点,但重复结点最坏是n²,log n²=2 log n,并不改变时间复杂度的数量级。

想一想,还能不能把时间复杂度再降低呢?如果我们使用斐波那契堆,那么松弛操作的时间复杂度O(1),总的时间复杂度为O(n* logn+E)。

附源代码1

#include <cstdio>#include <iostream>#include<cstring>#include<windows.h>#include<stack>using namespace std; // 1 数据结构const int N = 100; //城市的个数可修改const int INF = 1e7; //初始化无穷大为10000000int map[N][N],dist[N],p[N],n,m;//n城市的个数,m为城市间路线的条数bool flag[N]; //如果flag[i]等于true,说明顶点i已经加入到集合S;否则顶点i属于集合V-Svoid Dijkstra(int u){ // 2 初始化 for(int i=1; i<=n; i++) // ① { dist[i] =map[u][i]; //初始化源点u到其他各个顶点的最短路径长度 flag[i]=false; if(dist[i]==INF) p[i]=-1; //源点u到该顶点的路径长度为无穷大,说明顶点i与源点u不相邻 else p[i]=u; //说明顶点i与源点u相邻,设置顶点i的前驱p[i]=u } dist[u] = 0; flag[u]=true; //初始时,集合S中只有一个元素:源点u for(int k=1; k<=n; k++) //② { // 3 在集合V-S(!flag[m])中找距离源点u最近的顶点t int temp = INF,t = u; for(int m=1; m<=n; m++) //③ 在集合V-S中寻找距离源点u最近的顶点t if(!flag[m]&&dist[m]<temp) { t=m; temp=dist[m]; } if(t==u) return ; //找不到t,跳出循环 flag[t]= true; //否则,将t加入集合 // 4 找到t点后,更新从源点u经t后到集合V-S中与t邻接的顶点的距离 for(int j=1;j<=n;j++) //④ 更新集合V-S中与t邻接的顶点到源点u的距离 if(!flag[j]&& map[t][j]<INF)//!flag[j]表示j在V-S中 if(dist[j]>(dist[t]+map[t][j])) { dist[j]=dist[t]+map[t][j] ; p[j]=t ; } }}void findpath(int u){ int x; stack<int>s; //利用C++自带的函数创建一个栈s cout<<"源点为:"<<u<<endl; for(int i=1;i<=n;i++) { x=p[i]; while(x!=-1) { s.push(x); //将前驱依次压入栈中 x=p[x]; } cout<<"源点到其他各顶点最短路径为:"; while(!s.empty()) { cout<<s.top()<<"→"; //依次取栈顶元素 s.pop(); //出栈 } cout<<i<<";最短距离为:"<<dist[i]<<endl; }}int main(){ int u,v,w,st; //system("color 0d"); cout << "请输入城市的个数:"<<endl; cin >> n; cout << "请输入城市之间的路线的个数:"<<endl; cin >>m; cout << "请输入城市之间的路线以及距离:"<<endl; for(int i=1;i<=n;i++) //初始化图的邻接矩阵 for(int j=1;j<=n;j++) { map[i][j]=INF; //初始化邻接矩阵为无穷大 } while(m--) { cin >> u >> v >> w; map[u][v] =min(map[u][v],w); //邻接矩阵储存,保留最小的距离 } cout <<"请输入小明所在的位置:"<<endl; cin >> st; cout <<"输出矩阵map:"<<endl; for(int c=1;c<=n;c++) { for(int d=1;d<=n;d++) { if(map[c][d]==INF) cout << "\t" << "∞"; else cout << "\t" << map[c][d]; if(d==n) cout<<endl; } } Dijkstra(st); cout <<"小明所在的位置:"<<st<<endl; for(int k=1;k<=n;k++){ cout <<"小明:"<<st<<" - "<<"要去的位置:"<<k<<endl; if(dist[k] == INF) cout << "sorry,无路可达"<<endl; else cout << "最短距离为:"<<dist[k]<<endl; } findpath(st); //主函数中st为源点 system("pause"); return 0;}附源码2

#include <queue>#include <iostream>#include<cstring>#include<windows.h>using namespace std;const int N = 100; // 城市的个数可修改const int INF = 1e7; // 无穷大int map[N][N],dist[N],n,m;int flag[N];struct Node{ int u,step; Node(){}; Node(int a,int sp){ u=a; step=sp; } bool operator < (const Node& a)const{ // 重载 < return step>a.step; }};void Dijkstra(int st){ priority_queue <Node> Q; // 优先队列优化 Q.push(Node(st,0)); memset(flag,0,sizeof(flag)); //初始化flag数组为0 for(int i=1;i<=n;++i) dist[i]=INF; // 初始化所有距离为,无穷大 dist[st]=0; while(!Q.empty()) { Node it=Q.top(); //优先队列队头元素为最小值 Q.pop(); int t=it.u; if(flag[t]) //说明已经找到了最短距离,该结点是队列里面的重复元素 continue; flag[t]=1; for(int i=1;i<=n;i++) { if(!flag[i]&&map[t][i]<INF){ // 判断与当前点有关系的点,并且自己不能到自己 if(dist[i]>dist[t]+map[t][i]) { // 求距离当前点的每个点的最短距离,进行松弛操作 dist[i]=dist[t]+map[t][i]; Q.push(Node(i,dist[i]));// 把更新后的最短距离压入优先队列,注意:里面的元素有重复 } } } }}int main(){ int u,v,w,st; system("color 0d"); //设置背景及字体颜色 cout << "请输入城市的个数:"<<endl; cin >> n; cout << "请输入城市之间的路线的个数:"<<endl; cin >>m; for(int i=1;i<=n;i++) //初始化图的邻接矩阵 for(int j=1;j<=n;j++) { map[i][j]=INF; //初始化邻接矩阵为无穷大 } cout << "请输入城市之间u,v的路线以及距离w:"<<endl; while(m--) { cin>>u>>v>>w; map[u][v]=min(map[u][v],w); //邻接矩阵储存,保留最小的距离 } cout<<"请输入小明所在的位置:"<<endl; ; cin>>st; Dijkstra(st); cout <<"小明所在的位置:"<<st<<endl; for(int k=1;k<=n;k++) { cout <<"小明:"<<st<<"--->"<<"要去的位置:"<<k; if(dist[k]==INF) cout << "sorry,无路可达"<<endl; else cout << " 最短距离为:"<<dist[k]<<endl; } system("pause"); return 0;}参考:://blog.csdn.net/rainchxy/article/details/77978029

-End-

本文标签:C++图解

原文链接:https://www.xgfox.com/jsyd/31.html

本文版权:如无特别标注,本站文章均为原创。