在用floyd算法求解各顶点的最短路径时（c语言floyd算法求最短路径）

本文实例为大家分享了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; }