07-图6 旅游规划 (25 分)
前言：这篇文章是我的每日一文计划的第七篇文章，已经完成了一周的记录，在废物了几周之后感觉又一次找到了点好好学习的动力和不废物的目标感，希望自己能长期坚持！
PS:在文末我又立了点Flag👀👀，希望过一段时间以后这个Flag能够达成！🥳
题目描述
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入格式:
输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。
输出格式:
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
1
2
3
4
5
6
7
| 4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
//结尾无空行
|
输出样例:
题目理解与思路
本题题目理解起来不难，每个城市即为图的节点，每个城市之间的公路距离即为图的边
难点在于如何优先使用距离来判断路径，然后距离相同时使用收费额来作为判断的第二依据
本文使用邻接矩阵来存储图，使用Dijkstra算法来动态更新每个节点的最短路径，同时动态更新路径的花销（在计算最短路径的过程中就优先把价格更低的选择为当前路径），在Dijkstra算法计算完成后，保留的最短路径也就是花销最小的路径。代码如下
代码
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include<stdio.h>
#include<stdlib.h>
#define MaxVer 505
#define Inf 65535
typedef int Vertex;
typedef int Edge;
typedef int Distance;
typedef int Fare;
typedef struct GNode* PtrToGraph;
struct GNode
{
Vertex V;
Edge E;
Distance G[MaxVer][MaxVer];
Fare F[MaxVer][MaxVer];
};
typedef PtrToGraph MGraph;
Fare cost[MaxVer];
Distance Dist[MaxVer];
char collected[MaxVer] = {0};
MGraph BuildGraph(int V, int E);
void Dijkstra(MGraph Graph,Vertex Start,Vertex Destina);
int main(){
Vertex Start,Destina;
int V,E;
MGraph Graph;
scanf("%d %d %d %d\n",&V,&E,&Start,&Destina);
Graph = BuildGraph(V,E);
Dijkstra(Graph,Start,Destina);
return 0;
}
void Dijkstra(MGraph Graph,Vertex Start,Vertex Destina)
{
int i,MinDist,Min;
for(i = 0; i < Graph->V;i++)
if(Graph->G[Start][i] < Inf)
{
Dist[i] = Graph->G[Start][i];
cost[i] = Graph->F[Start][i];
}
collected[Start] = 1;
while(1){
Min = Inf;
for(i = 0;i < Graph->V;i++)
if( Dist[i] < Min && collected[i] == 0)
{
MinDist = i;
Min = Dist[i];
}
if(Min == Inf)break;
collected[MinDist] = 1;
for(i = 0; i < Graph->V;i++)
{
if(Graph->G[MinDist][i] < Inf)
if(collected[i] == 0)
{
if(Dist[MinDist] + Graph->G[MinDist][i] < Dist[i])
{
Dist[i] = Dist[MinDist] + Graph->G[MinDist][i];
cost[i] = cost[MinDist] + Graph->F[MinDist][i];
}
if((Dist[MinDist] + Graph->G[MinDist][i] == Dist[i])
&& ( cost[MinDist] + Graph->F[MinDist][i] < cost[i]))
{
cost[i] = cost[MinDist] + Graph->F[MinDist][i];
}
}
}
}
printf("%d %d\n",Dist[Destina],cost[Destina]);
return;
}
MGraph BuildGraph(int V, int E)
{
int i,j,D,F;
Vertex V1,V2;
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode));
Graph->V = V;
Graph->E = E;
for(i = 0;i < Graph->V; i++)
for(j = 0;j < Graph->V; j++)
{
if(i == j)
Graph->G[i][j] = Graph->F[i][j] = 0;
else
{
Graph->F[i][j] = Graph->G[i][j] = Inf;
}
}
for(i = 0;i < Graph->E; i++)
{
scanf("%d %d %d %d\n",&V1,&V2,&D,&F);
Graph->G[V1][V2] = Graph->G[V2][V1] = D;
Graph->F[V1][V2] = Graph->F[V2][V1] = F;
}
for(i = 0; i < Graph->V; i++)
{
Dist[i] = Inf;
cost[i] = 0;
}
return Graph;
}
|
后记——对于Dijkstra算法与Floyd算法的一些理解
学习了图这种数据结构之后一直想知道怎么运用这个数据结构不过一直没学到相关的算法，正好最近学了一些就写了点相关的题目，也有了些自己的新的理解。
Dijkstra算法
Dijkstra算法是用来求单个源点到其它所有点的距离的最小值的算法，使用最小堆来存储未收录点时查找最小点的复杂度为$O(logV)$（适合稀疏图），使用暴力的遍历所有节点查找最小值时复杂度为$O(V^2)$（适合稠密图），其思想是一种贪心算法，把节点分为了收录的和未收录的，收录的节点包含源点s和已经确定了最短路径的节点，每次收录一个节点，该节点也为已经缺定最短路径的节点，然后更新受新收录的节点影响的点到源点的距离和路径，而同时又可以证明收录的节点只会影响其邻接点的最小距离，故只需更新其邻接点的最小距离即可。由于每次收录的节点均为经过当前收录节点而确定的当前到源点距离最小的点（贪心），故保证了收录的所有节点均为确定了最短路径的节点。当所有的节点均收录完毕后，源点到所有对应点的距离也就确定了。
总结而言，Dijkstra算法就是每个循环都做以下三件事，直至所有节点都已被收录
- 选择未收录节点中距离源点最小的节点收录
- 收录后根据收录节点到源点的距离与图中其邻接边的权重来判断是否对邻接点有影响
- 更新邻接点的最小距离
Floyd算法
Floyd算法是用来求多个源点到其它所有点的最短路径的算法，对于稠密图来说效果更好一点，复杂度为$O(V^{3})$，其思想是动态规划的思想，每次迭代就比较源点 I 到一个节点K的距离加上K到目标节点 J 的距离是否小于源点 I 直接到目标节点 J 的距离，小于的时候就动态更新节点 J 的路径和最小距离，通过多次迭代来留下最小的各点到各点的距离值。
附记
从今日开始，增肌期结束💪，我将进入减脂期，会在每天的文章最后更新当日的体重噢🤸🏻🤸🏻🤸🏻
