songsong的垃圾堆

收废铜烂铁~

0%

图的应用--最短路径

发表于 更新于 阅读： Valine：
本文字数： 3k 阅读时长 ≈ 11 分钟

1. 从某个源点到其余各点的最短距离

  • 迪杰斯特拉（Dijkstra）算法

    • 将顶点集V分为两堆—-S 和 V-S，初始时S只有源点。

    • 辅助数组

      • S[i]==true/1，表示顶点加入了S集中。
      • Path[i]，其值记录着当前路径上vi的直接前驱顶点序号。
      • D[i]，从源点v0到终点vi的的当前最短路径长度。这与最小生成树 普利姆（prim） 算法中的辅助数组相似。只不过这里是路径，比较的是中转和非中转路线的权值，而最小生成树中，比较的是集合中（可能v0，v1）的点到其余各个顶点（可能v2，v3）的权值谁小（v0v2与v1v2、v0v3与v1v3比）。
      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
      void ShortestPath_DIJ(int v0) 		// 迪杰斯特拉算法最短路径
      {	
      	int v,w,i;	
      	int S[NUM]={0};	
      	int min;	
      	for(v=1;v<G.vexnum;v++){		//初始化 
      		S[v]=0;						//初始化为空集 
      		D[v]=G.arcs[v0][v].adj;		//将v0到各个终点的长度初始化为权值	
      		if(D[v]<Max){				//如果v0和V之间有边，将V的前驱置为v0 
      			path[v]=v0;		
      		}
      		else path[v]=-1;	 		//如果没有边，即没路 
      	}
      	D[v0]=0;						//源点到原点的距离为0 
      	S[v0]=1;						//将v0加入S
      	
      	/* 初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加入S中*/ 
      	
      	for(i=2;i<G.vexnum;++i){		//对其余n-1个顶点依次进行计算 
      		min=Max;	
      		for(w=1;w<G.vexnum;++w)				
      			if(!S[w]&&D[w]<min){	//选择一条当前的最短路径
      				v=w;			
      				min=D[w];		
      			}	    
      		S[v]=1;						//将v加入S 
      		
      		for(w=1;w<G.vexnum;++w)		//更新v0到集合V-S上所有顶点的最短路径长度 
      		if(!S[w]&&((D[v]+G.arcs[v][w].adj)<D[w])){		//中转路径更小 
      			D[w]=D[v]+G.arcs[v][w].adj;		
      			path[w]=v;		
      		}
      	}
      }

    • 输出路径

      从终点回溯到起点，path[i]的值是vi的前驱，只要前驱不等于起点，就一直回溯即可得到最短路径。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      if(sight1!=sight2){
      	printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);	
      	printf("\t(最短距离为 %dm.)\n\n\t",D[sight2]);	
          printf("%s<--",G.vex[sight2].sight);
      	while(path[end]!=sight1){
      		end=path[end];
      		printf("%s<--",G.vex[end].sight);	
      		q=q+1;		
      		if(q%8==0) printf("\n");
      	}
      	printf("%s",G.vex[sight1].sight);
      }

      回到顶部

      2. 每一对顶点之间的最短距离

      很显然，调用n次迪杰斯特拉（Dijkstra）算法即可得到任意两地间的最短距离。还有一种方法就是下面的弗洛伊德（Floyed）算法。

  • 弗洛伊德（Floyed）算法

    • 理解的不是很透彻，只能从宏观把握一下。两点间距离最小，要么有中转要么没有中转，所以肯定要比较加入中间点的路径长度。两个for循环，那只能输出二维数组的值（即两地间的距离），所以还需要一个for循环来插入中转点，然后比较找最短路径距离。
    • 辅助数组
      path[i][j]，其值记录了i，j确定的顶点的前驱。
      D[i][j]，记录了vi到vj的最短路径长度。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      void ShortestPath_Floyed(){			//求各对顶点之间的最短路径
      	int P[NUM][NUM];				//记录路径
      	int Dis[NUM][NUM];				//记录最短路径  
      	int i,j,k,q=0;	
      	int end;
      	for(i=1;i<G.vexnum;i++){		//初始化 
      		for(j=1;j<G.vexnum;j++){
      			if(i==j) Dis[i][j]=0;
      			else Dis[i][j]=G.arcs[i][j].adj;
      			if(Dis[i][j]<Max) P[i][j]=i;	//如果i和j之间有边，将j的前驱置为i
      			else P[i][j]=-1;
      		}
      	}
      	
      	for(k=1;k<G.vexnum;k++)
      		for(i=1;i<G.vexnum;i++)
      			for(j=1;j<G.vexnum;j++)	
      				if(Dis[i][k]+Dis[k][j]<Dis[i][j]){	
      					Dis[i][j]=Dis[i][k]+Dis[k][j];		
      					P[i][j]=P[k][j];	
      				}
      }

    • 输出路径

      从终点回溯到起点，path[i][j]的值是vj的前驱，只要前驱不等于起点vi，就一直回溯即可得到最短路径。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      for(i=1;i<G.vexnum;i++){	
      		for(j=1;j<G.vexnum;j++){	
      			end=j;		
      			printf("\n从%s到%s的最短路径是",G.vex[i].sight,G.vex[j].sight);	
      			printf("\t(最短距离为 %dm.)\n\t",Dis[i][j]);	
      		    printf("\n%s<--",G.vex[j].sight);
      			while(P[i][end]!=i){
      				end=P[i][end];
      				printf("%s<--",G.vex[end].sight);	
      				q=q+1;		
      				if(q%8==0) printf("\n");
      			}
      			printf("%s\n",G.vex[i].sight);
      		}
      	}
      回到顶部

      总的代码：

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
#define Max 32767
#define NUM 13

typedef char ArcType; 
typedef char VerType; 

typedef struct ArcCell{
	int adj;				//记录权值 
	ArcType *info;			//其他信息 
}ArcCell;

typedef struct VertexType{
	int number;     		//顶点编号
	VerType *sight;			//其他信息，在此记录顶点名 即地名 
}VertexType;

typedef struct{
	VertexType vex[NUM];	//顶点表 
	ArcCell arcs[NUM][NUM];	//邻接矩阵 
	int vexnum,arcnum;    	//点数和边数 
}MGraph;

MGraph G;


int D[NUM];									//记录最短路径 
int path[NUM];								//记录路径 
void CreateUDN(int v,int a);				//创建图	
void ShortestPath_DIJ(int num);				//求最短路径	
void ShortestPath_Floyed();					//求各对顶点之间的最短路径 
void printpath(int sight1,int sight2);		//输出任意两点间的最短路径 
void lookAllArc();							//浏览任意两地边的信息 
void lookSingleArc();						//浏览单一边的信息
void modify(); 								//修改两个位置之间的距离 
void welcome();
char Menu();

void CreateUDN(int v,int a) // 创建图的函数
{
	int i,j;
	G.vexnum=v;
	G.arcnum=a;
	for(i=1;i<G.vexnum;++i) G.vex[i].number=i;
	G.vex[0].sight="初始化";
	G.vex[1].sight="西苑门口";
	G.vex[2].sight="男生宿舍17A公寓";
	G.vex[3].sight="第三食堂";
	G.vex[4].sight="大学生活动中心";
	G.vex[5].sight="西苑图书馆";
	G.vex[6].sight="篮球场";
	G.vex[7].sight="教学楼区";
	G.vex[8].sight="计算机学院办公楼";
	G.vex[9].sight="中苑门口";
	G.vex[10].sight="医务室";
	G.vex[11].sight="中苑图书馆";
	G.vex[12].sight="体育馆";
	
	for(i=1;i<G.vexnum;++i){
		for(j=1;j<G.vexnum;++j){	
			G.arcs[i][j].adj=Max;		//初始化权值为最大，即不通路	
			G.arcs[i][j].info=NULL;	
		}	
	}
	
	G.arcs[1][4].adj=G.arcs[4][1].adj=500;	
	G.arcs[1][3].adj=G.arcs[3][1].adj=500;	
	G.arcs[3][5].adj=G.arcs[5][3].adj=100;	
	G.arcs[9][10].adj=G.arcs[10][9].adj=400;	
	G.arcs[4][6].adj=G.arcs[6][4].adj=100;	
	G.arcs[2][5].adj=G.arcs[5][2].adj=400;	
	G.arcs[2][4].adj=G.arcs[4][2].adj=300;	
	G.arcs[5][7].adj=G.arcs[7][5].adj=100;	
	G.arcs[4][6].adj=G.arcs[6][4].adj=100;	
	G.arcs[4][7].adj=G.arcs[7][4].adj=200;	
	G.arcs[6][8].adj=G.arcs[8][6].adj=300;
	G.arcs[7][8].adj=G.arcs[8][7].adj=200;	
	G.arcs[1][9].adj=G.arcs[9][1].adj=10;
	G.arcs[10][11].adj=G.arcs[11][10].adj=400;
	G.arcs[11][12].adj=G.arcs[12][11].adj=300;	
}

void modify(){
	int sight1,sight2,length;
	printf("\n\t\t请输入要修改的两地：\n");	
	scanf("%d %d",&sight1,&sight2);
	if(sight1<1||sight1>12||sight2<1||sight2>12){
		printf("\n\t\t请输入正确的地名序号~\n");
	}
	else if(sight2!=sight1){
		if(G.arcs[sight1][sight2].adj<Max){
			printf("\n\t请输入从%s到%s的最新路径长度",G.vex[sight1].sight,G.vex[sight2].sight);	
			scanf("%d",&length);
			if(length<Max){
				G.arcs[sight1][sight2].adj=length;
				G.arcs[sight2][sight1].adj=	G.arcs[sight1][sight2].adj;
				printf("\t修改成功！\n");
			} 
			else	printf("\t请输入有效的路径长度\n");	
		}
		else printf("这两地之间没有通路，不能修改！\n");		
	}
	else printf("请输入有意义的两地！\n"); 
} 

void lookAllArc(){	
	int i,j,n=0; 
	printf("\n所有边的信息如下：\n");	
	for(i=1;i<NUM;++i){
		for(j=1;j<NUM;++j){
			if(G.arcs[i][j].adj<Max){
				n++;
				printf("从%s到%s的路径长度是%d\n",G.vex[i].sight,G.vex[j].sight,G.arcs[i][j].adj); 
			}	
			else {
				n++;
				printf("从%s到%s没有直接的路~\n",G.vex[i].sight,G.vex[j].sight); 
			}
		}	
	}
	printf("\n\n累计%d条记录\n\n",n);
}

void lookSingleArc(){
	int i,j,n=0; 
	int v0,v1; 
	printf("\n\n\t\t请选择一端的序号（1～12）：");		
	scanf("%d",&v0);		
	printf("\t\t请选择另一端的序号（1～12）：");		
	scanf("%d",&v1);
	if(v0<1||v0>12||v1<1||v1>12){
		printf("\n\t\t请输入正确的地名序号~\n");
	}			
	else if(G.arcs[v0][v1].adj<Max){
		printf("\n\t\t从%s到%s的路径长度是%dm\n",G.vex[v0].sight,G.vex[v1].sight,G.arcs[v0][v1].adj); 
	}	
	else {
		printf("\n\t\t从%s到%s没有直接的路~\n",G.vex[v0].sight,G.vex[v1].sight); 
	}		
}
 
void ShortestPath_DIJ(int v0) 		// 迪杰斯特拉算法最短路径
{	
	int v,w,i;	
	int S[NUM]={0};	
	int min;	
	for(v=1;v<G.vexnum;v++){		//初始化 
		S[v]=0;						//初始化为空集 
		D[v]=G.arcs[v0][v].adj;		//将v0到各个终点的长度初始化为权值	
		if(D[v]<Max){				//如果v0和V之间有边，将V的前驱置为v0 
			path[v]=v0;		
		}
		else path[v]=-1;	 		//如果没有边，即没路 
	}
	D[v0]=0;						//源点到原点的距离为0 
	S[v0]=1;						//将v0加入S
	
	/* 初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加入S中*/ 
	
	for(i=2;i<G.vexnum;++i){		//对其余n-1个顶点依次进行计算 
		min=Max;	
		for(w=1;w<G.vexnum;++w)				
			if(!S[w]&&D[w]<min){	//选择一条当前的最短路径
				v=w;			
				min=D[w];		
			}	    
		S[v]=1;						//将v加入S 
		
		for(w=1;w<G.vexnum;++w)		//更新v0到集合V-S上所有顶点的最短路径长度 
			if(!S[w]&&((D[v]+G.arcs[v][w].adj)<D[w])){	//中转路径更小 
				D[w]=D[v]+G.arcs[v][w].adj;		
				path[w]=v;		
			}
	}
}

void ShortestPath_Floyed(){			//求各对顶点之间的最短路径
	int P[NUM][NUM];				//记录路径
	int Dis[NUM][NUM];				//记录最短路径  
	int i,j,k,q=0;	
	int end;
	for(i=1;i<G.vexnum;i++){		//初始化 
		for(j=1;j<G.vexnum;j++){
			if(i==j) Dis[i][j]=0;
			else Dis[i][j]=G.arcs[i][j].adj;
			if(Dis[i][j]<Max) P[i][j]=i;	//如果i和j之间有边，将j的前驱置为i
			else P[i][j]=-1;
		}
	}
	
	for(k=1;k<G.vexnum;k++)
		for(i=1;i<G.vexnum;i++)
			for(j=1;j<G.vexnum;j++)	
				if(Dis[i][k]+Dis[k][j]<Dis[i][j]){	
					Dis[i][j]=Dis[i][k]+Dis[k][j];		
					P[i][j]=P[k][j];	
				}
	
	for(i=1;i<G.vexnum;i++){	
		for(j=1;j<G.vexnum;j++){	
			end=j;		
			printf("\n从%s到%s的最短路径是",G.vex[i].sight,G.vex[j].sight);	
			printf("\t(最短距离为 %dm.)\n\t",Dis[i][j]);	
		    printf("\n%s<--",G.vex[j].sight);
			while(P[i][end]!=i){
				end=P[i][end];
				printf("%s<--",G.vex[end].sight);	
				q=q+1;		
				if(q%8==0) printf("\n");
			}
			printf("%s\n",G.vex[i].sight);
		}
	}
}

void printpath(int sight1,int sight2) // 输出函数
{	
	int q=0;	
	int end=sight2;	
	if(sight1<1||sight1>12||sight2<1||sight2>12){
		printf("\n\t\t请输入正确的地名序号~\n");
	}
	else if(sight1!=sight2){
		printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);	
		printf("\t(最短距离为 %dm.)\n\n\t",D[sight2]);	
	    printf("%s<--",G.vex[sight2].sight);
		while(path[end]!=sight1){
			end=path[end];
			printf("%s<--",G.vex[end].sight);	
			q=q+1;		
			if(q%8==0) printf("\n");
		}
		printf("%s",G.vex[sight1].sight);
	}
	else{
		printf("\n\t\t\t从%s到%s的距离为0m\n",G.vex[sight1].sight,G.vex[sight2].sight);	
	}
}

void welcome() //登录图标
{
	int i=0; 
	printf("\t\t■■■■■■■■■■■■■■■■■■■■■■■\n");
	printf("\t\t■                                          ■\n");
	printf("\t\t■  ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■  ■\n");	
	printf("\t\t■                                          ■\n");
	printf("\t\t■  ■ 欢迎来到X X X X 大学校园导航系统 ■  ■\n");	
	printf("\t\t■                                          ■\n");
	printf("\t\t■  ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■  ■\n");
	printf("\t\t■                                          ■\n");
	printf("\t\t■■■■■■■■■■■■■■■■■■■■■■■\n\n");
	for(i=1;i<NUM;i++){
		printf("\t\t\t\t(%2d)%-20s\t\t\t\n",i,G.vex[i].sight);	
	}
}

void show(){
	int i,j=0;
	for(i=0;i<G.vexnum;i++){
		for(j=0;j<G.vexnum;j++){
			printf("%8d",G.arcs[i][j].adj);
		}
		printf("\n");
	}
}
 
int main() // 主函数
{ 
 
	int v0,v1;
	char ck;
	CreateUDN(NUM,15);
	//show();
	do{
		ck=Menu();
		switch(ck){			
			case '1':		
				welcome();		
				printf("\n\n\t\t\t请选择出发地序号（1～12）：");		
				scanf("%d",&v0);		
				printf("\t\t\t请选择目的地序号（1～12）：");		
				scanf("%d",&v1);		
				ShortestPath_DIJ(v0);		
				printpath(v0,v1);		
				printf("\n\n\t\t请按回车键继续...\n");			
				getchar();		
				getchar();		
				break;
			case'2':	
				lookAllArc();				
				getchar();
				getchar();	
			 	break;
			case'3':				
				modify();		
				getchar();
				getchar();	
			 	break;
			case'4':				
				ShortestPath_Floyed();		
				getchar();
				getchar();	
			 	break;	 
			case'5':				
				lookSingleArc();		
				getchar();
				getchar();	
			 	break;	 	 	
			case'6':				
				printf("\n\n有待实现更多功能\n\n");		
				getchar();
				getchar();	
			 	break;	
		};	
	}while(ck!='e');
	return 0;
}

char Menu() // 主菜单
{
	char c;
	int flag;
	do{
		welcome();
		flag=1;			
		printf("\t 操作： \n");
		printf("\t┏----------------------------┓\n");
		printf("\t│ 1.导航                     │\n");	
		printf("\t│ 2.查看所有边的路径长度     │\n");	
		printf("\t│ 3.修改路径长度             │\n");	
		printf("\t│ 4.查看各地间的最短路径长度 │\n");	
		printf("\t│ 5.查看单一边的路径长度     │\n");
		printf("\t│ e.退出                     │\n");		
		printf("\t┗----------------------------┛\n");
		printf("\t\t请输入您的选择：");	
		scanf("%c",&c);	
		if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='e')	
			flag=0;		
	}while(flag);	
	return c;
}

回到顶部

运行结果：

![在这里插入图片描述](https://img-blog.csdnimg.cn/20190715100310587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Nvbmdzb25nTA==,size_16,color_FFFFFF,t_70 =600x)
迪杰斯特拉（Dijkstra）算法求起点到终点最短路径：
在这里插入图片描述
弗洛伊德（Floyed）算法求任意两地间的最短距离：
在这里插入图片描述
回到顶部

------------- Thank you for reading -------------
Title - Artist
0:00