本文实例为大家分享了C++所有顶点之间最短路径的具体代码，供大家参考，具体内容如下
一、思路： 不能出现负权值的边
用Floyd算法，总的执行时间为O(n的3次方）
k从顶点0一直到顶点n-1，
如果，有顶点i到顶点j之间绕过k，使得两顶点间的路径更短，即dist[i][k] + dist[k][j] < dist[i][j]，则修改：dist[i][j]
如：（1）当k=0时，
顶点2绕过顶点0到达顶点1，使得路径为：3+1 < dist[2][1]，所以，要修改dist[2][1]=4,同时要修改path[2][1]=path[0][1];
顶点2绕过顶点0到达顶点3，使得路径为：3+4 < dist[2][3]，所以，要修改dist[2][1]=7,同时要修改path[2][3]=path[0][3];
（2）当k=1时，
顶点2绕过顶点1到达顶点3，使得路径为：2->0->1->3，3+1+2=6 <dist[2][3]=7,所以，要修改dist[2][3]=6,同时要修改path[2][3]=path[1][3];
一直重复上面步骤，直到k=6
二、实现程序：
1.Graph.h:有向图
|
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
|
#ifndef Graph_h#define Graph_h#include <iostream>using namespace std; const int DefaultVertices = 30; template <class T, class E>struct Edge { // 边结点的定义 int dest; // 边的另一顶点位置 E cost; // 表上的权值 Edge<T, E> *link; // 下一条边链指针}; template <class T, class E>struct Vertex { // 顶点的定义 T data; // 顶点的名字 Edge<T, E> *adj; // 边链表的头指针}; template <class T, class E>class Graphlnk {public: const E maxValue = 100000; // 代表无穷大的值（=∞） Graphlnk(int sz=DefaultVertices); // 构造函数 ~Graphlnk(); // 析构函数 void inputGraph(); // 建立邻接表表示的图 void outputGraph(); // 输出图中的所有顶点和边信息 T getValue(int i); // 取位置为i的顶点中的值 E getWeight(int v1, int v2); // 返回边（v1， v2）上的权值 bool insertVertex(const T& vertex); // 插入顶点 bool insertEdge(int v1, int v2, E weight); // 插入边 bool removeVertex(int v); // 删除顶点 bool removeEdge(int v1, int v2); // 删除边 int getFirstNeighbor(int v); // 取顶点v的第一个邻接顶点 int getNextNeighbor(int v,int w); // 取顶点v的邻接顶点w的下一邻接顶点 int getVertexPos(const T vertex); // 给出顶点vertex在图中的位置 int numberOfVertices(); // 当前顶点数private: int maxVertices; // 图中最大的顶点数 int numEdges; // 当前边数 int numVertices; // 当前顶点数 Vertex<T, E> * nodeTable; // 顶点表(各边链表的头结点)}; // 构造函数:建立一个空的邻接表template <class T, class E>Graphlnk<T, E>::Graphlnk(int sz) { maxVertices = sz; numVertices = 0; numEdges = 0; nodeTable = new Vertex<T, E>[maxVertices]; // 创建顶点表数组 if(nodeTable == NULL) { cerr << "存储空间分配错误！" << endl; exit(1); } for(int i = 0; i < maxVertices; i++) nodeTable[i].adj = NULL;} // 析构函数template <class T, class E>Graphlnk<T, E>::~Graphlnk() { // 删除各边链表中的结点 for(int i = 0; i < numVertices; i++) { Edge<T, E> *p = nodeTable[i].adj; // 找到其对应链表的首结点 while(p != NULL) { // 不断地删除第一个结点 nodeTable[i].adj = p->link; delete p; p = nodeTable[i].adj; } } delete []nodeTable; // 删除顶点表数组} // 建立邻接表表示的图template <class T, class E>void Graphlnk<T, E>::inputGraph() { int n, m; // 存储顶点树和边数 int i, j, k; T e1, e2; // 顶点 E weight; // 边的权值 cout << "请输入顶点数和边数：" << endl; cin >> n >> m; cout << "请输入各顶点：" << endl; for(i = 0; i < n; i++) { cin >> e1; insertVertex(e1); // 插入顶点 } cout << "请输入图的各边的信息：" << endl; i = 0; while(i < m) { cin >> e1 >> e2 >> weight; j = getVertexPos(e1); k = getVertexPos(e2); if(j == -1 || k == -1) cout << "边两端点信息有误，请重新输入！" << endl; else { insertEdge(j, k, weight); // 插入边 i++; } } // while} // 输出有向图中的所有顶点和边信息template <class T, class E>void Graphlnk<T, E>::outputGraph() { int n, m, i; T e1, e2; // 顶点 E weight; // 权值 Edge<T, E> *p; n = numVertices; m = numEdges; cout << "图中的顶点数为" << n << ",边数为" << m << endl; for(i = 0; i < n; i++) { p = nodeTable[i].adj; while(p != NULL) { e1 = getValue(i); // 有向边<i, p->dest> e2 = getValue(p->dest); weight = p->cost; cout << "<" << e1 << ", " << e2 << ", " << weight << ">" << endl; p = p->link; // 指向下一个邻接顶点 } }} // 取位置为i的顶点中的值template <class T, class E>T Graphlnk<T, E>::getValue(int i) { if(i >= 0 && i < numVertices) return nodeTable[i].data; return NULL;} // 返回边（v1， v2）上的权值template <class T, class E>E Graphlnk<T, E>::getWeight(int v1, int v2) { if(v1 != -1 && v2 != -1) { if(v1 == v2) // 说明是同一顶点 return 0; Edge<T , E> *p = nodeTable[v1].adj; // v1的第一条关联的边 while(p != NULL && p->dest != v2) { // 寻找邻接顶点v2 p = p->link; } if(p != NULL) return p->cost; } return maxValue; // 边(v1, v2)不存在,就存放无穷大的值} // 插入顶点template <class T, class E>bool Graphlnk<T, E>::insertVertex(const T& vertex) { if(numVertices == maxVertices) // 顶点表满，不能插入 return false; nodeTable[numVertices].data = vertex; // 插入在表的最后 numVertices++; return true;} // 插入边template <class T, class E>bool Graphlnk<T, E>::insertEdge(int v1, int v2, E weight) { if(v1 == v2) // 同一顶点不插入 return false; if(v1 >= 0 && v1 < numVertices && v2 >= 0 && v2 < numVertices) { Edge<T, E> *p = nodeTable[v1].adj; // v1对应的边链表头指针 while(p != NULL && p->dest != v2) // 寻找邻接顶点v2 p = p->link; if(p != NULL) // 已存在该边，不插入 return false; p = new Edge<T, E>; // 创建新结点 p->dest = v2; p->cost = weight; p->link = nodeTable[v1].adj; // 链入v1边链表 nodeTable[v1].adj = p; numEdges++; return true; } return false;} // 有向图删除顶点较麻烦template <class T, class E>bool Graphlnk<T, E>::removeVertex(int v) { if(numVertices == 1 || v < 0 || v > numVertices) return false; // 表空或顶点号超出范围 Edge<T, E> *p, *s; // 1.清除顶点v的边链表结点w 边<v,w> while(nodeTable[v].adj != NULL) { p = nodeTable[v].adj; nodeTable[v].adj = p->link; delete p; numEdges--; // 与顶点v相关联的边数减1 } // while结束 // 2.清除<w, v>，与v有关的边 for(int i = 0; i < numVertices; i++) { if(i != v) { // 不是当前顶点v s = NULL; p = nodeTable[i].adj; while(p != NULL && p->dest != v) {// 在顶点i的链表中找v的顶点 s = p; p = p->link; // 往后找 } if(p != NULL) { // 找到了v的结点 if(s == NULL) { // 说明p是nodeTable[i].adj nodeTable[i].adj = p->link; } else { s->link = p->link; // 保存p的下一个顶点信息 } delete p; // 删除结点p numEdges--; // 与顶点v相关联的边数减1 } } } numVertices--; // 图的顶点个数减1 nodeTable[v].data = nodeTable[numVertices].data; // 填补,此时numVertices，比原来numVertices小1，所以，这里不需要numVertices-1 nodeTable[v].adj = nodeTable[numVertices].adj; // 3.要将填补的顶点对应的位置改写 for(int i = 0; i < numVertices; i++) { p = nodeTable[i].adj; while(p != NULL && p->dest != numVertices) // 在顶点i的链表中找numVertices的顶点 p = p->link; // 往后找 if(p != NULL) // 找到了numVertices的结点 p->dest = v; // 将邻接顶点numVertices改成v } return true;} // 删除边template <class T, class E>bool Graphlnk<T, E>::removeEdge(int v1, int v2) { if(v1 != -1 && v2 != -1) { Edge<T, E> * p = nodeTable[v1].adj, *q = NULL; while(p != NULL && p->dest != v2) { // v1对应边链表中找被删除边 q = p; p = p->link; } if(p != NULL) { // 找到被删除边结点 if(q == NULL) // 删除的结点是边链表的首结点 nodeTable[v1].adj = p->link; else q->link = p->link; // 不是，重新链接 delete p; return true; } } return false; // 没有找到结点} // 取顶点v的第一个邻接顶点template <class T, class E>int Graphlnk<T, E>::getFirstNeighbor(int v) { if(v != -1) { Edge<T, E> *p = nodeTable[v].adj; // 对应链表第一个边结点 if(p != NULL) // 存在，返回第一个邻接顶点 return p->dest; } return -1; // 第一个邻接顶点不存在} // 取顶点v的邻接顶点w的下一邻接顶点template <class T, class E>int Graphlnk<T, E>::getNextNeighbor(int v,int w) { if(v != -1) { Edge<T, E> *p = nodeTable[v].adj; // 对应链表第一个边结点 while(p != NULL && p->dest != w) // 寻找邻接顶点w p = p->link; if(p != NULL && p->link != NULL) return p->link->dest; // 返回下一个邻接顶点 } return -1; // 下一个邻接顶点不存在} // 给出顶点vertex在图中的位置template <class T, class E>int Graphlnk<T, E>::getVertexPos(const T vertex) { for(int i = 0; i < numVertices; i++) if(nodeTable[i].data == vertex) return i; return -1;} // 当前顶点数template <class T, class E>int Graphlnk<T, E>::numberOfVertices() { return numVertices;} #endif /* Graph_h */ |
2.Floyd.h
|
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
|
#ifndef Floyd_h#define Floyd_h#include "Graph.h"#include <stack> // Floyd算法template <class T, class E>void Floyd(Graphlnk<T, E> &G, E dist[][DefaultVertices], int path[][DefaultVertices]) { // Graph是一个带权有向图，dist[]是当前求到的从顶点v到顶点j的最短路径长度，同时用数组 // path[]存放求到的最短路径 // dist[i][j]表示顶点i到顶点j的最短路径的权值 int n = G.numberOfVertices(); // 顶点数 int i, j, k; for(i = 0; i < n; i++) { // 矩阵dist与path初始化 for(j = 0; j < n; j++) { dist[i][j] = G.getWeight(i, j); if(i != j && dist[i][j] < G.maxValue) path[i][j] = i; // 从顶点i到j的最短路径初始化，j的上一个顶点为i else path[i][j] = -1; // 没有<i,j>的边 } } for(k = 0; k < n; k++) { // 有n个顶点，需要进行n次更新dist(k)和path(k) for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = path[k][j]; // 缩短路径长度，绕过k到j } } } }} // 从path数组读取最短路径的算法template <class T, class E>void printShortestPath(Graphlnk<T, E> &G, E dist[][DefaultVertices], int path[][DefaultVertices]) { int i, j, k, n = G.numberOfVertices(); stack<int> st; // 记忆路径 for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(i != j) { // 如果不是顶点自身 cout << "从顶点" << G.getValue(i) << "到顶点" << G.getValue(j) << "的最短路径为："; if(path[i][j] == -1) { // 表示两者之间不存在通路 cout << "顶点" << G.getValue(i) << "到顶点" << G.getValue(j) << "不存在路径！" << endl; } else { // 存在路径 // 要把顶点存到栈中，倒过来输出路径 k = j; do { k = path[i][k]; st.push(k); // 把顶点k压入栈中 }while(k != i); while(st.empty() == false) { // 当栈不空时 k = st.top(); // 退栈 st.pop(); cout << G.getValue(k) << "->"; } cout << G.getValue(j) << "，长度为：" << dist[i][j] << endl; } } } // for内循环 } // for外循环}#endif /* Floyd_h */ |
3.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
|
/* 测试数据： 4 8 0 1 2 3 0 1 1 0 3 4 1 2 9 1 3 2 2 0 3 2 1 5 2 3 8 3 2 6 */ #include "Floyd.h" int main(int argc, const char * argv[]) { Graphlnk<char, int> G; // 声明图对象 int dist[DefaultVertices][DefaultVertices], path[DefaultVertices][DefaultVertices]; // 创建图 G.inputGraph(); cout << "图的信息如下：" << endl; G.outputGraph(); // 求所有顶点之间的最短路径 Floyd(G, dist, path); // 输出各个顶点之间的最短路径 printShortestPath(G, dist, path); return 0;} |
测试结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/chuanzhouxiao/article/details/88908754
