实验4 最短路径
实验时间
4课时。
实验目的
- 练习结对编程。
- 掌握图的存储结构。
- 掌握Dijkstra算法或Floyd算法。
问题描述
给定全国铁路网，对于任意一对城市，找出它们之间的最短路径经过哪些城市，并输出最短路径的长度。
铁路网的信息以文本形式给出，其格式为：
城市A编号 城市B编号 距离
其中城市编号和城市名称信息也是以文本形式给出，其格式为：
编号 城市名称
这两个文本文件可以在下方zip文件处与源码一起下载。
实验内容
- 两人一对，提交一份实验报告和源代码。
- 求出下列城市之间的最短路径：沈阳至西安、呼和浩特至成都、上海至乌鲁木齐。
- 从铁路网中删除一些城市（例如郑州），再重新计算上述城市之间的最短路径。
实现提示
图的存储结构可使用邻接矩阵（较为简单）或邻接表。
源代码
下载源代码
main.cpp mgraph.h mgraph.cpp
若程序显示无法打开文件，请在mgraph.cpp第10行和第27行自行修改文件路径名；
本程序使用Floyd算法实现。
main.cpp
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
|
#include"mgraph.h"
int main()
{
mgraph G;
G.vexnum=0;
for(int i=0;i<maxvertices;i++)
for(int j=0;j<maxvertices;j++)
G.edge[i][j]=maxweight;
create(G);
while(1){
printf(" << =================== 功 能 选 择 ================ >> \n\n");
printf("【1】 ： 两地间最短路径\n");
printf("【2】 ： 删除城市\n");
printf("【3】 ： 退出程序 \n");
printf("请选择功能 ： ");
int ch;
scanf("%d", &ch);
while(getchar()!='\n') continue;
switch (ch)
{
case 1:
shortpath(G);
break;
case 2:
while (1)
{
printf("【a】 ： 删除城市 \n\n");
printf("【b】 ： 最短路径 \n\n");
printf("【c】 ： 返回主菜单 \n\n");
printf(" 请选择功能 :");
char ch2;
scanf("%c", &ch2);
while(getchar()!='\n') continue;
switch (ch2)
{
case 'a':
int n;
printf("请输入要删除的城市编号：");
scanf("%d",&n);
while(getchar()!='\n') continue;
for(int i=0;i<=G.vexnum;i++){
G.edge[i][n]=maxweight;
G.edge[n][i]=maxweight;
}
continue;
case 'b':
shortpath(G);
continue;
case 'c':
create(G);
printf("铁路网已复原\n");
break;
default:
{
printf("输入有误，请重新输入!\n");
continue;
}
}
break;
}
break;
case 3:
exit(0);
default:
{
printf("功能选择错误，请重新选择正确的选项 ! \n");
break;
}
}
}
}
|
mgraph.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#ifndef GRAPH_MGRAPH_H
#define GRAPH_MGRAPH_H
#include<stdio.h>
#include<stdlib.h>
#include<string.h>//strcmp
#include<math.h>
#define maxvertices 100
#define maxweight 32767
typedef int weight;
typedef struct{
int vexnum;
weight edge[maxvertices][maxvertices];
}mgraph;
extern void create(mgraph &G);
extern void shortpath(mgraph &G);
#endif
|
mgraph.cpp
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
|
#include "mgraph.h"
void create(mgraph &G){
FILE *in;
FILE *in2;
int d=0;
int i,j;
if((in=fopen("/home/wxxxx/桌面/clion-2020.2.4/CLionProjects/zuiduanlujing/dist.txt","r"))==NULL)
{
printf("无法打开dist文件\n");
exit(0);
}
int arcnumber=0;
int vexnumber=0;
while((fscanf(in,"%d %d %d",&i,&j,&d)>0)){
if(vexnumber<i)
vexnumber=i;
if(vexnumber<j)
vexnumber=j;
arcnumber++;
G.edge[i][j]=d;
G.edge[j][i]=d;
}
G.vexnum=vexnumber;
if((in2=fopen("/home/wxxxx/桌面/clion-2020.2.4/CLionProjects/graph/city.txt","r"))==NULL)
{
printf("无法打开city文件\n");
exit(0);
}
printf("邻接矩阵:\n");
printf(" ");
for(i=0;i<=G.vexnum;i++)
{
printf("%4d",i);
}
printf("\n");
for(i=0;i<=G.vexnum;i++)
{
printf("%2d",i);
for(j=0;j<=G.vexnum;j++)
{
if(G.edge[i][j]<maxweight)
{
printf("%4d",G.edge[i][j]);
}
else
{
printf(" #");
}
}
printf("\n");
}
printf("其中对应关系:\n");
char c;
while(fscanf(in2,"%c",&c)!=EOF) printf("%c",c);
fclose(in);
fclose(in2);
}
void shortpath(mgraph &G)
{
weight d[maxvertices][maxvertices];
int path[maxvertices][maxvertices];
int i,j,k;
for(i=0;i<=G.vexnum;i++)
for(j=0;j<=G.vexnum;j++){
d[i][j]=G.edge[i][j];
path[i][j]=j;
}
for(k=0;k<=G.vexnum;k++)
for(i=0;i<=G.vexnum;i++)
for(j=0;j<=G.vexnum;j++){
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[i][k];
}
}
for(i=0;i<=G.vexnum;i++)
d[i][i]=0;
printf("城市距离表:\n");
printf(" ");
for(i=0;i<=G.vexnum;i++)
{
printf("%5d",i);
}
printf("\n");
for(i=0;i<=G.vexnum;i++)
{
printf("%5d",i);
for(j=0;j<=G.vexnum;j++)
{
if(d[i][j]<maxweight)
{
printf("%5d",d[i][j]);
}
else
{
printf(" # ");
}
}
printf("\n");
}
int f,en;
printf("请输入出发地编号和终点编号：");
scanf("%d%d",&f,&en);
while(getchar()!='\n') continue;
if(d[f][en]>=maxweight){
printf("从此天各一方！\n");
}
else {
while (f != en) {
printf("%d->", f);
f = path[f][en];
}
printf("%d\n", en);
}
}
|
