👉最短路径👈
路径：在图 G = (V， E) 中，若从顶点 vi 出发有一组边使其可到达顶点 vj，则称顶点 vi 到顶点 vj 的顶点序列为从顶点 vi 到顶点 vj 的路径。
路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和。
最短路径问题：从在带权有向图 G 中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。单源最短路径问题是给点一个起点，求出起点到其他点的最短路径；而多源最短路径问题就是求出图中任意两点的最多路径。
Dijkstra算法
namespace matrix { class Graph { typedef Graph<V, W, W_MAX, Direction> Self; // ... public: // Dijkstra的时间复杂度为O(N^2),空间复杂度为O(N) void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath) { size_t srci = GetVertexIndex(src); size_t n = _vertexs.size(); // 初始状态 dist.resize(n, W_MAX); pPath.resize(n, -1); dist[srci] = W(); pPath[srci] = srci; // 已经确定最短路径的顶点集合S vector<bool> S(n, false); for (size_t i = 0; i < n; ++i) { // 选出未确定最短路径的顶点,用已经确定最短路径的顶点去 // 更新其他顶点的最短路径 int u = 0; // u是已经确定最短路径的顶点(注:存在错位) W min = W_MAX; for (size_t j = 0; j < n; ++j) { if (S[j] == false && dist[j] < min) { u = j; min = dist[j]; } } S[u] = true; // 松弛更新u连接顶点v srci->u + u->v < srci->v 更新 // v是还未确定最短路径的顶点 for (size_t v = 0; v < n; ++v) { // Dijkstra算法只能确定没有负权的图的最短路径 // 原因是没有负权,当前已经确定的最短路径肯定 // 是该顶点的最短路径。而存在负权的话,可能多 // 走几个顶点的路径长度会比当前确定的最短路径 // 的长度还要短。所以Dijkstra算法只能确定没有 // 负权的图的最短路径 if (S[v] == false && _matrix[u][v] != W_MAX && dist[u] + _matrix[u][v] < dist[v]) { dist[v] = dist[u] + _matrix[u][v]; pPath[v] = u; } } } } // 打印最短路径 void PrintShortPath1(const V& src, const vector<W>& dist, const vector<int>& pPath) { size_t srci = GetVertexIndex(src); size_t n = _vertexs.size(); for (size_t i = 0; i < n; ++i) { if (i != srci) { // 生成从起点srci到顶点i的最短路径 vector<int> path; size_t parenti = i; while (parenti != srci) { path.push_back(parenti); parenti = pPath[parenti]; } path.push_back(srci); reverse(path.begin(), path.end()); cout << "从起点" << src << "到顶点" << _vertexs[i] << "的最短路径为" << dist[i] << endl; cout << "路径为"; for (auto index : path) { cout << _vertexs[index]; if (index != *(path.end() - 1)) cout << "->"; } cout << endl << "---------------------------" << endl; } } } } }
Dijkstra 算法无法解决有负权的图
void GraphDijkstraTest2() { // 图中带有负权路径时，贪心策略则失效了。 // 测试结果可以看到s->t->y之间的最短路径没更新出来 const char* str = "sytx"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('s', 't', 10); g.AddEdge('s', 'y', 5); g.AddEdge('t', 'y', -7); g.AddEdge('y', 'x', 3); vector<int> dist; vector<int> parentPath; g.Dijkstra('s', dist, parentPath); g.PrintShortPath('s', dist, parentPath); }
Dijkstra 算法用已经确定最短路径的顶点来更新未确定最短路径的顶点。
BellmanFord算法
BellmanFord 算法的优化是通过队列来优化的，将更新的更短的路径入队列，从而更新包含该路径的路径。优化后，BellmanFord 算法的最好情况是 O(N^2)，最坏情况是 O(N^3)。
负权回路问题
namespace matrix { class Graph { // ... public: // BellmanFord算法的时间复杂度为O(N^3),空间复杂度为O（N） bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath) { size_t n = _vertexs.size(); size_t srci = GetVertexIndex(src); // vector<W> dist,记录srci-其他顶点最短路径权值数组 dist.resize(n, W_MAX); // vector<int> pPath 记录srci-其他顶点最短路径父顶点数组 pPath.resize(n, -1); // 先更新srci->srci为缺省值 dist[srci] = W(); // 总体最多更新n轮 for (size_t k = 0; k < n; ++k) { // 顶点i到顶点j 更新一次 bool update = false; //cout << "更新第:" << k << "轮" << endl; for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { // dist[i]为起点srci到i的距离,_matrix[i][j]为i到j的距离 if (_matrix[i][j] != W_MAX && dist[i] + _matrix[i][j] < dist[j]) { update = true; //cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl; dist[j] = dist[i] + _matrix[i][j]; pPath[j] = i; } } } // 如果这个轮次中没有更新出更短路径，那么后续轮次就不需要再走了 if (update == false) { break; } } // 还能更新就是存在负权回路 for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { // srci -> i + i ->j if (_matrix[i][j] != W_MAX && dist[i] + _matrix[i][j] < dist[j]) { return false; } } } return true; // 不存在负权回路 } } void GraphBellmanFordTest() { const char* str = "syztx"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('s', 't', 6); g.AddEdge('s', 'y', 7); g.AddEdge('y', 'z', 9); g.AddEdge('y', 'x', -3); g.AddEdge('z', 's', 2); g.AddEdge('z', 'x', 7); g.AddEdge('t', 'x', 5); g.AddEdge('t', 'y', 8); g.AddEdge('t', 'z', -4); g.AddEdge('x', 't', -2); // 存在负权回路的样例 /*const char* str = "syztx"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('s', 't', 6); g.AddEdge('s', 'y', 7); g.AddEdge('y', 'z', 9); g.AddEdge('y', 'x', -3); g.AddEdge('y', 's', 1); // 新增 g.AddEdge('z', 's', 2); g.AddEdge('z', 'x', 7); g.AddEdge('t', 'x', 5); g.AddEdge('t', 'y', -8); //更改 g.AddEdge('t', 'z', -4); g.AddEdge('x', 't', -2);*/ vector<int> dist; vector<int> parentPath; if (g.BellmanFord('s', dist, parentPath)) g.PrintShortPath('s', dist, parentPath); else cout << "存在负权回路,无法求出最短路径" << endl; } }
FloydWarshall算法
即 Floyd 算法本质是三维动态规划，D[i][j][k] 表示从点 i 到点 j 只经过 0 到 k 个点最短路径，然后建立起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得到所以点的最短路。
namespace matrix { class Graph { // ... public: // FloydWarshall算法的时间复杂度为O(N^3),空间复杂度为O(N^2) void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath) { size_t n = _vertexs.size(); vvDist.resize(n); vvpPath.resize(n); // 初始化权值和路径矩阵 for (size_t i = 0; i < n; ++i) { vvDist[i].resize(n, W_MAX); vvpPath[i].resize(n, -1); } // 直接相连的边更新一下 for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { if (_matrix[i][j] != W_MAX) { vvDist[i][j] = _matrix[i][j]; vvpPath[i][j] = i; } // 自己到自己的距离为默认值 if (i == j) vvDist[i][j] = W(); } } // abcdef：a {中间节点} f 或 b {中间节点} c // 最短路径的更新：i->{其他顶点}->j for (size_t k = 0; k < n; ++k) { for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { // k作为的中间点尝试去更新i->j的路径 // vvDist[i][j]是从i到j的最短路径的长度 // vvpPath[i][j]中存的是从i到j路径上与j直接相连的顶点下标 if (vvDist[i][k] != W_MAX && vvDist[k][j] != W_MAX && vvDist[i][k] + vvDist[k][j] < vvDist[i][j]) { vvDist[i][j] = vvDist[i][k] + vvDist[k][j]; // 找出跟j相连的上一个邻接顶点 // 如果k和j直接相连.上一个点就是k，vvpPath[k][j]存就是k // 如果k和j没有直接相连,k->...->x->j,vvpPath[k][j]存就是x // vvpPath[k][j]中存的是从k到j路径上与j直接相连的顶点下标 vvpPath[i][j] = vvpPath[k][j]; } } } // 打印权值和路径矩阵观察数据 /* for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { if (vvDist[i][j] == W_MAX) { //cout << "*" << " "; printf("%3c", '*'); } else { //cout << vvDist[i][j] << " "; printf("%3d", vvDist[i][j]); } } cout << endl; } cout << endl; for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < n; ++j) { //cout << vvParentPath[i][j] << " "; printf("%3d", vvpPath[i][j]); } cout << endl; } cout << "=================================" << endl; */ } } } void FloydWarShallTest() { const char* str = "12345"; Graph<char, int, INT_MAX, true> g(str, strlen(str)); g.AddEdge('1', '2', 3); g.AddEdge('1', '3', 8); g.AddEdge('1', '5', -4); g.AddEdge('2', '4', 1); g.AddEdge('2', '5', 7); g.AddEdge('3', '2', 4); g.AddEdge('4', '1', 2); g.AddEdge('4', '3', -5); g.AddEdge('5', '4', 6); vector<vector<int>> vvDist; vector<vector<int>> vvParentPath; g.FloydWarshall(vvDist, vvParentPath); // 打印任意两点之间的最短路径 for (size_t i = 0; i < strlen(str); ++i) { // 一维数组vvDist[i]是从顶点i到其他点的最短路径的距离 // 一维数组vvParentPath[i]是从顶点i到其他点的最短路径 g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]); cout << endl; } } }
总结
Dijkstra 算法只能求出没有负权的图的最短路径，时间复杂度为 O(N^3)。BellmanFord 算法能够求出有负权的图的最短路径，时间复杂度为 O(N^3)。但存在负权回路问题，任何算法都无法解决负权回路问题。Dijkstra 算法和 BellmanFord 算法都需要给点起点，求得的是从起点到其他点的最短路径；而 FloydWarshall 算法能够求出任意两点之间的最短路径，时间复杂度为 O(N^3)。图论中的重点内容是图重要的基本概念、邻接矩阵和邻接表的优缺点、广度优先遍历和深度优先遍历、最小生成树和最短路径等。
👉总结👈
本篇博客主要讲解了最小生成树的 Kruskal 算法和 Prim 算法以及最短路径的 Dijkstra 算法、BellmanFord 算法和 FloydWarshall 算法等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
