Fork me on GitHub

数据结构与算法-图论(三)-最短路径


数据结构与算法-图论(三)-最短路径

​ 在讨论完最小生成树后,我们再来了解图论中另一个经典问题:最短路径问题。即寻找图中某两个特定结点间最短的路径长度。所谓图上的路径,即从图中一个起始终点到一个终止终点途中经过的所有结点序列,路径的长度即所经过的边权和。

​ 最短路径问题在实际中的应用也非常广泛,例如确定某两个城市间的最短行车路线长度。要解决这类问题,我们要根据图的特点和问题的特征选择不同的算法。

我们首先来介绍第一种计算最短路径长度的算法-Floyd算法

1
2
3
4
5
for(k=1;k<=n;k++)  
for(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];

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

题目描述:

在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,非常累!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?

输入:

输入包括多组数据。每组数据第一行是两个整数N,M(N <= 100,M <= 10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1 <= A,B <= N, 1 <= C <= 1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。当输入为两个0时,输入结束。

输出:

对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间。

样例输入:

1
2
3
4
5
6
7
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

样例输出:

1
2
3
2

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>

using namespace std;

#define 101 N
int ans[N][N];

int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
if(n == 0 && m == 0) break;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
ans[i][j] = -1; // 对邻接矩阵初始化,我们用-1代表无穷
}
ans[i][i] = 0; // 自己到自己的路径长度设为0
}
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
ans[a][b] = ans[b][a] = c; // 对邻接矩阵赋值,由于是无向图,该赋值操作要进行两次
}
for(int k = 1 ; k <= n ; k++){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
if(ans[i][k] == -1 || ans[k][j] == -1)
continue; // 若两值中有一个值为无穷,则ans[i][j]不能由于经过结点k而被更新,跳过循环,保持原值
if(ans[i][j] == -1 || ans[i][k] + ans[k][j] < ans[i][j])
ans[i][j] = ans[i][k] + ans[k][j];
// 当由于进过k可以获得更短的最短路径时,更新该值
}
}
}
printf("%d\n",ans[1][n]); // 循环结束后输出答案
}
return 0;
}

运行结果:

对于Floyd算法具体理解可以参考这篇博客:https://www.cnblogs.com/wangyuliang/p/9216365.html

​ 我们总结Floyd算法的特点。第一,牢记其时间复杂度为O(N^3),所以在大部分机试题的时间允许范围内,他要求被求解图的大小不大于200个结点,若超过该数字该算法很可能因为效率不够高而被判超时。第二,Floyd算法利用一个二维矩阵来进行相关运算,所以当图使用邻接矩阵表示时更为方便。若原图并非由邻接矩阵给出时我们设法将其转换,注意当两个节点间有多余一条边时,选择长度最小的边权值存入邻接矩阵。第三,当Floyd算法完成后,图中所有结点之间的最短路径都将被确定。所以,其较适用于要求询问多个结点对之间的最短路径长度问题,即全源最短路径问题。了解它的这些特点,将有利于我们在特定问题中决定是否使用Floyd算法。

​ 在讨论完Floyd算法后,我们来看另一种与其特点完全不同的最短路径算法-Dijkstra算法(迪杰斯特拉算法)。它与之间讨论的Floyd算法有一个非常明显的区别,Floyd算法可以计算出图中所有结点对之间的最短路径长度,Dijkstra算法只能求得某特定结点到其他所有结点的最短路径长度,即单源最短路径问题。

关于Dijstra算法的具体理解可以参考这篇博客:https://www.cnblogs.com/wangyuliang/p/9216511.html

我们使用Dijstra算法重写上例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct E{ // 邻接链表中链表元素结构体
int next; // 代表直接相邻的结点
int c; // 代表该边的权值(长度)
};
vector<E> edge[101]; // 邻接链表
bool mark[101]; // 标记,当mark[j]为true时表示结点j的最短路径长度已经得到,该结点已经加入集合K
int Dis[101]; // 距离向量,当mark[i]为true时,表示已得的最短路径长度;否则,表示所有从结点1出发,经过已知的最短路径达到集合K中的某结点
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
if(n == 0 && m == 0) break;
for(int i = 1 ; i <= n ; i++) edge[i].clear(); // 初始化邻接链表
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
E tmp;
tmp.c = c;
tmp.next = b;
edge[a].push_back(tmp);
tmp.next = a;
edge[b].push_back(tmp);
// 将邻接信息加入邻接链表,由于原图为无向图,固每条边信息都要添加到其两个顶点的两条单链表中
}
for(int i = 1 ; i <= n ; i++){
Dis[i] = -1; // 所有距离为-1,即不可达
mark[i] = false; // 所有结点不属于集合K
}
Dis[1] = 0; // 得到最近的点为结点1,长度为0
mark[1] = true; // 将结点1加入集合K
int newP = 1; // 集合K中新加入的点为结点1
for(int i = 1 ; i < n ; i++){// 循环n-1次,按照最短路径递增的顺序确定其他n-1个点的最短路径长度
for(int j = 0 ; j < edge[newP].size() ; j++){
int t = edge[newP][j].next; // 该边的另一个结点
int c = edge[newP][j].c; // 该边的长度
if(mark[t] == true) continue; // 若另一个结点也属于集合K,则跳过
if(Dis[t] == -1 || Dis[t] > Dis[newP]+c) // 若该结点尚不可达,或者该结点从新加入的结点经过一条边到达时比以往距离更短
Dis[t] = Dis[newP] + c;
}
int min = 123123123; // 最小值初始化为一个大整数,为找最小值做准备
for(int j = 1 ; j <= n ; j++){// 遍历所有结点
if(mark[j] == true) continue;
if(Dis[j] == -1) continue;
if(Dis[j] < min){
min = Dis[j];
newP = j; // 新加入的点暂定为该点
}
}
mark[newP] = true;
}
printf("%d\n",Dis[n]);
}
}

运行结果:

如代码所示,我们用mark[i]的值来确定结点i的最短路径是否已经被确定,并根据结点i是否属于集合K,Dis[i]中的数字体现出不同的意义。当结点i属于集合K时,Dis[i]代表结点i已经被确定的最短路径长度;相反,若结点i不属于集合K,那么Dis[i]表示,所有从结点1出发先按照某条最短路径到达已经在集合K中的结点,并由该结点经过一条边到达结点i路径中的最短距离。

总之就是将新加入进K集合的点的所有出边进行“松弛”,然后在“松弛”完后的非K集合中寻找距离最小的点加入集合K,并将新加入的点标记。

我们再来看一个例题:

题目描述:

给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。

输入:

输入n,m,点的编号是1~n,然后m行,每行4个数a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数s,t;起点s,终点t。n和m为0时输入结束。

输出:

输出一行有两个数:最短距离及其花费。

样例输入:

1
2
3
4
5
3 2
1 2 5 6
2 3 4 5
1 3
0 0

样例输出:

1
9 11

​ 在该例中,我们不仅需要求得起点到终点的最短距离,还需要在有多条最短路径时,选取花费最少的那一条。要解决这个问题,只要更改Dijstra算法中关于“更近”的评判标准即可:有两条路径,若他们距离不一样时,距离小的更近;若距离一样时花费少的更近。当定义这种新的评判标准后,Dijstra算法照样能为我们求得“最近”的路径长度。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct E{// 邻接链表元素结构体
int next;
int c;
int cost;
};
vector<E> edge[1001]; // 邻接链表
int Dis[1001]; // 距离数组
int cost[1001]; // 花费数组
bool mark[1001]; // 是否属于集合K数组

int main(){
int n,m;
int S,T; // 起点,终点
while(scanf("%d%d",&n,&m)!=EOF){
if(n == 0 && m == 0) break;
for(int i = 1 ; i <= n ; i++) edge[i].clear(); // 初始化邻接链表
while(m--){
int a,b,c,cost;
scanf("%d%d%d%d",&a,&b,&c,&cost);
E tmp;
tmp.c = c;
tmp.cost = cost;
tmp.next = b;
edge[a].push_back(tmp);
tmp.next = a;
edge[b].push_back(tmp);
}
scanf("%d%d",&S,&T);
for(int i = 1 ; i <= n ; i++){
Dis[i] = -1;
mark[i] = false;
}
Dis[S] = 0;
mark[S] = true;
int newP = S; // 起点为S,将其加入集合K,且其最短距离确定为0
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < edge[newP].size(); j++){
int t = edge[newP][j].next;
int c = edge[newP][j].c;
int co = edge[newP][j].cost; // 花费
if(mark[t] == true) continue;
if(Dis[t] == -1 || Dis[t] > Dis[newP] + c || Dis[t] == Dis[newP] + c && cost[t] > cost[newP]+co){
Dis[t] = Dis[newP] + c;
cost[t] = cost[newP] + co;
}
}
int min = 123123123;
for(int j = 1 ; j <= n ; j++){
if(mark[j] == true) continue;
if(Dis[j] == -1) continue;
if(Dis[j] < min){
min = Dis[j];
newP = j;
}
}
mark[newP] = true;
}
printf("%d %d\n",Dis[T],cost[T]); // 输出答案
}
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%