数据结构 基于Dijsktra算法的最短路径求解_一张地图包括n个城市,假设城市间有m条路径(有向图),每条路径的长度已知。给定地图

实验目的

1.掌握图的邻接矩阵表示法，掌握采用邻接矩阵表示法创建图的算法。
2.掌握求解最短路径的Dijsktra 算法。

实验内容

问题描述
一张地图包括n个城市，假设城市间有m条路径(有向图)，每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。
输入要求
多组数据，每组数据有m+3行。第一行为两个整数n和m,分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个 整数d,代表从城市a到城市b有一条距离为d的路。最后一行为两个字符，代表待求最短路径的城市起点和终点。当n和m都等于0时，输入结束。
输出要求
每组数据输出2行。第1行为一个整数，为从起点到终点之间最短路的长度。第2行为一串字符串，代表该路径。每两个字符之间用空格隔开。
输入样例

3 3
A B C
A B 1
B C 1
C A 3
A C
6 8
A B C D E F 
A F 100
A E 30
A C 10
B C 5
C D 50
D E 20
E F 60
D F 10
A F
0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

输出样例

2
A B C
60
A E D F
1
2
3
4

实验提示

此实验内容即为主教材算法6.10的扩展内容,算法6.10求出源点v0到图中其余所有顶点的最短路径。本实验要求求出一个指定起点到一个指定终点的最短路径。
为了提高算法的效率，在求解时，可以加以判断，当已求得的终点为指定终点时，则可以终止求解，按要求输出相应结果。

源代码

#include <iostream>
using namespace std;

//____图的邻接矩阵存储表示____
#define MaxInt 32567 //表示极大值，即正无穷
#define MVNum 100 //最大定点数
#define OK 1
typedef char VerTexType;//假设顶点的数据类型为字符型 vertex顶点
typedef int ArcType;//假设边的权值类型为整型
typedef struct {
	VerTexType vexs[MVNum];//顶点表
	ArcType arcs[MVNum][MVNum];//邻接矩阵
	int vexnum, arcnum;//图的当前点数和边数
}AMGraph;

VerTexType IndexVex(AMGraph G, int u) {//存在则返回u在顶点表中的下标，否则返回-1
	return G.vexs[u];
}

int LocateVex(AMGraph G, VerTexType v) {
	for (int i = 0; i < G.vexnum; i++) {
		if (v == G.vexs[i])//输入的顶点v在G中找到
			return i;
	}
	return -1;
}

int CreateUDN(AMGraph& G) {//采用邻接矩阵表示法，创建无向网G
	char v1, v2;
	int w;
	cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	for (int i = 0; i < G.vexnum; ++i)
		cin >> G.vexs[i];
	for (int i = 0; i < G.vexnum; ++i)//初始化邻接矩阵，边的最大权值设置为极大值MaxInt
		for (int j = 0; j < G.vexnum; ++j)
			G.arcs[i][j] = MaxInt;
	int i, j;
	for (int k = 0; k < G.arcnum; ++k) {//构造邻接矩阵
		cin >> v1 >> v2 >> w;//输入一条边依附的顶点及权值
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
		G.arcs[i][j] = w;//边<v1,v2>的权值置为w
		G.arcs[j][i] = G.arcs[i][j];//置<v1,v2>的对称边<v2,v1>的权值为w
	}//for
	return OK;
}

int CreateDN(AMGraph& G,int vex,int edge) {//采用邻接矩阵表示法，创建有向网G
	char v1, v2;
	int w;
	//cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
	G.vexnum = vex;//总顶点数
	G.arcnum = edge;//总边数
	for (int i = 0; i < G.vexnum; ++i)
		cin >> G.vexs[i];
	for (int i = 0; i < G.vexnum; ++i)//初始化邻接矩阵，边的最大权值设置为极大值MaxInt
		for (int j = 0; j < G.vexnum; ++j)
			G.arcs[i][j] = MaxInt;
	int i, j;
	for (int k = 0; k < G.arcnum; ++k) {//构造邻接矩阵
		cin >> v1 >> v2 >> w;//输入一条边依附的顶点及权值
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
		G.arcs[i][j] = w;//边<v1,v2>的权值置为w
		//G.arcs[j][i] = G.arcs[i][j];//置<v1,v2>的对称边<v2,v1>的权值为w
	}//for
	return OK;
}
/*
* 迪杰斯特拉算法的实现
* 假设用带权的邻接矩阵arcs来表示带权有向网G,G.arcs[i][j]表示弧<vi,vj>上的权值。
* 若<vi,vj>不存在，则置G.arcs[i][j]为无穷大，源点v0
* 算法的实现要引入以下辅助的数据结构
* ①一维数组S[i]:记录从源点v0到终点vi是否已被确定最短路径长度，true表示确定，false表示尚未确定
* ②二维数组Path[i]:记录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号。
* 其初值为:如果从v0到vi有弧，则Path[i]为v0;否则为-1
* ③一维数组D[i]:记录从源点v0到终点vi的当前最短路径上vi的当前最短路径长度。其初值为:如果从v0
* 到vi有弧，则D[i]为弧上的权值；否则为正无穷
*/
int D[MVNum], Path[MVNum];
void ShortestPath_DIJ(AMGraph G, VerTexType V) {//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径
	int n, w, v, min;
	int S[MVNum];
	n = G.vexnum;//n是顶点的个数
	int v0 = LocateVex(G, V);
	for (v = 0; v < n; v++) {
		S[v] = false;//S初始为空集
		D[v] = G.arcs[v0][v];//将v0到各个终点的最短路径长度初始化为弧上的权值
		if (D[v] < MaxInt) {
			Path[v] = v0;//如果v0和v之间有弧，则将v前驱置为v0
		}
		else {
			Path[v] = -1;//如果v0和v之间无弧，则将v前驱置为-1
		}
	}//for
	S[v0] = true;//将v0加入S
	D[v0] = 0;//源点到源点的距离为0
	/*————————初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集————————*/
	for (int i = 1; i < n; i++) {//对其余n-1个顶点，依次进行计算
		min = MaxInt;
		for (w = 0; w < n; ++w) {
			if (!S[w] && D[w] < min) {
				v = w; min = D[w];//选择一条当前的最短路径，终点为v 
			}
		}
		S[v] = true;//将v加入S
		for (w = 0; w < n; w++) {//更新从v0出发到集合V-S上所有顶点的最短路径长度
			if (!S[w] && (D[v] + G.arcs[v][w] < D[w])) {
				D[w] = D[v] + G.arcs[v][w];//更新D[w]
				Path[w] = v;//更改w的前驱为v
			}//if
		}
	}//for
}

void Search(AMGraph G, int v) {
	if (Path[v] == -1)
		return;
	else {
		Search(G, Path[v]);
		cout << IndexVex(G, Path[v]) << " ";
	}
}

int main() {
	char city1, city2;//城市名字，起点、终点
	int a, b;//n个城市，m条路径
	while (cin >> a >> b && a && b) {
		AMGraph G;
		CreateDN(G, a, b);
		cin >> city1;
		ShortestPath_DIJ(G, city1);
		cin >> city2;
		int n = LocateVex(G, city2);
		cout << D[n] << endl;
		Search(G, n);
		cout << city2 << endl;
	}
	return 0;
}
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

运行截图