C++计算任意权值的单源最短路径（Bellman-Ford）

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
#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 */

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 Bellman_Ford_h
#define Bellman_Ford_h
#include "Graph.h"
 
// Bellman-Ford算法
template<class T, class E>
void BellmanFord(Graphlnk<T, E> &G, int v, E dist[], int path[]) {
 int i, k, u, n = G.numberOfVertices();
 E w;
 
 // 1.初始化，将顶点v作为u顶点（存在<v, u>有向边）的上一个顶点，记录路径
 for(i = 0; i < n; i++) {
  dist[i] = G.getWeight(v, i);
  if(i != v && dist[i] < G.maxValue)
   path[i] = v;
  else
   path[i] = -1;
 }
 // 2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点的最短距离估计值逐步逼近其最短距离；（运行n-1次,因为上面算是1次:k=1，所以，k从2开始）
 bool isFlag; // 监视该轮dist数组是否有变化
 for(k = 2; k < n; k++) {
  isFlag = false;
  for(u = 0; u < n; u++) { // 遍历顶点，找不是v的顶点
   if(u != v) {
    for(i = 0; i < n; i++) {
     w = G.getWeight(i, u);
     if(w != 0 && w < G.maxValue && dist[u] > dist[i] + w) {
      // 存在<i, u>边，并且绕过i,使得路径更短，就修改u顶点的最短路径
      // w可能是负权值，如果i和u是同一顶点，则w是0，排除同一顶点的情况
      // 也可以不写w!=0，因为同一顶点，w=0,dist[u]==dist[i]+w会不满足
      // dist[u] > dist[i] + w这个条件
      dist[u] = dist[i] + w;
      path[u] = i; // 记忆路径
      isFlag = true;
     }
    } // 第3重循环
   }
  } // 第2重循环
  if(isFlag == false) // 如果dist数组没有变化，说明各个顶点已求得最短路径
   break;
 } // 第1重for循环
}
 
// 从path数组读取最短路径的算法
template <class T, class E>
void printShortestPath(Graphlnk<T, E> &G, int v, E dist[], int path[]) {
 int i, j, k, n = G.numberOfVertices();
 int *d = new int[n];
 
 cout << "从顶点" << G.getValue(v) << "到其他各顶点的最短路径为：" << endl;
 for(i = 0; i < n; i++) {
  if(i != v) { // 如果不是顶点v
   j = i;
   k = 0;
   while(j != v) {
    d[k++] = j;
    j = path[j];
   }
   cout << "顶点" << G.getValue(i) << "的最短路径为：" << G.getValue(v);
   while(k > 0)
    cout << "->" << G.getValue(d[--k]);
   cout << "，最短路径长度为：" << dist[i] << endl;
  }
 }
}
#endif /* Bellman_Ford_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
/*
 测试数据：
 7 10
 0 1 2 3 4 5 6
 0 1 6
 0 2 5
 0 3 5
 1 4 -1
 2 1 -2
 2 4 1
 3 2 -2
 3 5 -1
 4 6 3
 5 6 3
 */
 
#include "Bellman-Ford.h"
 
const int maxSize = 40;
 
int main(int argc, const char * argv[]) {
 Graphlnk<char, int> G; // 声明图对象
 int dist[maxSize], path[maxSize], v;
 char u0;
 
 // 创建图
 G.inputGraph();
 cout << "图的信息如下：" << endl;
 G.outputGraph();
 cout << "请输入起始顶点u0:" << endl;
 cin >> u0;
 v = G.getVertexPos(u0); // 取得起始顶点的位置
 // 我把dist数组放到有向图头文件中，方便建立有向图时，同时初始化dist数组
 BellmanFord(G, v, dist, path); // 调用BellmanFord函数
 printShortestPath(G, v, dist, path); // 输出到各个顶点的最短路径
 return 0;
}