【数据结构与算法】图的最短路径算法实现：Dijkstra && Bellman-Ford && Floyd-Warshall
【数据结构与算法】图的最短路径算法实现：Dijkstra && Bellman-Ford && Floyd-Warshall
前言
最短路径问题：从在带权有向图 G 中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。
Ⅰ. 单源最短路径 – Dijkstra 迪杰克斯拉算法
单源最短路径问题：给定一个图
G=(V，E)，求源结点s∈V到图中每个结点v∈V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。
算法简介
Dijkstra 算法是用来解决 单源最短路径的算法，即在一个图中找出一个点 N，找出以该点为起点到其他所有点的最短路径。但是如果想找到两个顶点 A 和 C 之间的最短路径时，Dijkstra 算法可能同时找到到达其它顶点（例如顶点B）的最短路径，这一点将在算法演示的时候详细解释。同时 Dijkstra 算法 无法适用于含有负权重的图。
时间复杂度：O(V^2)
算法步骤
- 维护一个数组
dist来储存起点到各个顶点的最短距离，一个数组pPath来存储每个节点在最短路径中的上一个节点的下标（方便后面的打印），一个数组S来用bool值来表示每个节点是否已经被确定。 - 初始化上面的数组，
dist中起点默认为0，其他点默认为无穷大；pPath中起点默认为0，其他点默认为-1；S中默认所有点为false，表示还没被确定。 - 利用循环遍历
_vertexs.size()次，每次选择未确定顶点中距离最近的，将该点在S数组中设为true，表示确认了。 - 接着进行松弛调整，也就是找到与当前选择的顶点
u邻接的点k，计算数组dist中存储的到达k点的距离是否小于起点经过u到达k点的距离，即判断dist[u] + _matrix[u][k] <= dist[k]，是的话则更新邻接点k在dist中的值为dist[u] + _matrix[u][k]，并调整pPath中k点的父亲节点下标，否则继续寻找下一个与u相邻的点，重复该步骤直到遍历完u的所有邻接点。 - 重复步骤 3、4 直至遍历所有节点都访问过。
注意事项：
Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径- 为什么不采用优先级队列来找每次最短路径中的最小顶点呢❓❓❓ 因为我们在找到这个顶点后会做松弛算法，那么可能会调整到其他顶点的一个权值，所以这个时候我们也得更新优先级队列中的顶点权值，那也是比较麻烦的，所以这里采用简便一点的实现，直接使用循环，当然这样子时间复杂度会相对高一点！
代码实现
// Dijkstra算法
// 其中src代表单源节点
// dist数组是存放src到每个节点的最短路径距离
// pPath数组是存放每个节点的最短路径中的上一个节点下标
void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
// 一些初始化工作
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
dist[srci] = W(); // 将单源节点先设为默认值
pPath.resize(n, -1);
pPath[srci] = W();
// S中true表示该点已经确定
vector<bool> S(n, false);
// 这里采用直接遍历所有点，再在循环体中再来寻找最小值的方式
// 因为如果是用优先级队列的话，不好调整
for (size_t i = 0; i < n; ++i)
{
// 贪心算法：srci到不在S中路径最短的那个顶点u
size_t u = srci;
W min = MAX_W;
for (size_t j = 0; j < n; ++j)
{
if (S[j] == false && dist[j] < min)
{
u = j;
min = dist[j];
}
}
S[u] = true; // 将当前得到的节点设置为已确定
// 现在有了那个当前最短边的顶点的下标
// 所以我们直接遍历这个点的邻接点
// 并对这些邻接点进行松弛调整
for (size_t k = 0; k < n; ++k)
{
// 1、若邻接点为确定的节点了，那么不需要调整
// 2、若不相通也不需要调整
// 3、若当前权值加上与邻接点的边的权值大于了原来邻接点的权值，那么也不需要调整
if (S[k] == false
&& _matrix[u][k] != MAX_W
&& dist[u] + _matrix[u][k] < dist[k])
{
dist[k] = dist[u] + _matrix[u][k];
pPath[k] = u; // 注意别忘了更新路径
}
}
}
}
void PrintShortPath(const V& src, const vector<W>& dist, const vector<W>& pPath)
{
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
for (size_t i = 0; i < n; ++i)
{
if (srci != i)
{
vector<size_t> path;
size_t parenti = i;
while (parenti != srci)
{
path.push_back(parenti);
parenti = pPath[parenti];
}
path.push_back(srci);
// 先逆置一下，因为当前的访问顺序是从后到前的
reverse(path.begin(), path.end());
for (auto e : path)
{
cout << _vertexs[e] << "->";
}
cout << dist[i] << endl;
}
}
}
void TestGraphDijkstra()
{
const char* str = "syztx";
Graph<char, int, INT_MAX, true> g(str, strlen(str));
g.AddEdge('s', 't', 10);
g.AddEdge('s', 'y', 5);
g.AddEdge('y', 't', 3);
g.AddEdge('y', 'x', 9);
g.AddEdge('y', 'z', 2);
g.AddEdge('z', 's', 7);
g.AddEdge('z', 'x', 6);
g.AddEdge('t', 'y', 2);
g.AddEdge('t', 'x', 1);
g.AddEdge('x', 'z', 4);
vector<int> dist;
vector<int> parentPath;
g.Dijkstra('s', dist, parentPath);
g.PrintShortPath('s', dist, parentPath);
// 图中带有负权路径时，贪心策略则失效了。
// 测试结果可以看到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.PrinrtShotPath('s', dist, parentPath);
*/
}
// 运行结果：
s->y->5
s->y->z->7
s->y->t->8
s->y->t->x->9Ⅱ. 单源最短路径 – Bellman-Ford 贝尔曼-福特算法
Dijkstra 算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而 bellman—ford 算法 可以解决负权图的单源最短路径问题。它的优点是可以解决有负权边的单源最短路径问题，而且 可以用来判断是否有负权回路。它也有明显的缺点，它的 时间复杂度 O(N*E) (N是点数，E是边数) 普遍是要高于 Dijkstra 算法的。
像这里如果我们使用邻接矩阵实现，那么遍历所有边的数量的 时间复杂度就是 O(N^3)，这里也可以看出来 Bellman-Ford 就是一种暴力求解更新。
但 Bellman—Ford 算法可以进行若干种优化，提高效率，有兴趣的话可以了解一下（后边我们会加入第一种优化）：
- 循环的提前跳出
- 在实际操作中，贝尔曼-福特算法经常会在未达到
V-1次前就出解，V-1其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。
- 在实际操作中，贝尔曼-福特算法经常会在未达到
- 队列优化（
SPFA算法）
基本原理
逐遍的对图中每一条边去迭代计算起始点到其余各点的最短路径，执行 N-1 遍，最终得到起始点到其余各点的最短路径，有点类似于冒泡排序的思想。（N为连通图结点数）
与迪杰斯特拉算法的区别
- 迪杰斯特拉算法是借助 贪心思想，每次选取一个未处理的最近的结点，去对与他相连接的边进行松弛操作；贝尔曼福特算法是直接对所有边进行
N-1遍松弛操作，也就是 暴力破解。 - 迪杰斯特拉算法要求边的权值 不能是负数；贝尔曼福特算法边的权值 可以为负数，并 可检测负权回路。
名词解释
- 松弛操作：不断更新最短路径和前驱结点的操作。
- 负权回路：绕一圈绕回来发现到自己的距离从
0变成了负数，到各结点的距离无限制的降低，停不下来。
🔺 注意：负权回路是基本没有算法可以解决的问题，包括我们现实中也是，因为他会无限循环下去，没有最优解！
算法步骤
简单的说，就是把每个顶点拎出来，看作 n 个元素，然后利用类似冒泡排序的思想，遍历 n*n 遍，每次都去判断是否能更新成为更短的边。
并且为了防止后面更新的更短路径影响了前面已有的路径，我们要在最外面再加一层循环，重新再遍历一遍，这样子那些被影响的边就能重新更新，但是重新更新的边可能还会影响更前面的路径，所以我们总共要遍历 n 次。
我们还可以优化一下，利用 flag 判断是否是否有更新边，没有的话直接 break。
这样子暴力求解就能直接算出最短路径了，缺点就是时间复杂度太高，有兴趣的话可以去参考一下 SPFA 算法，专门用来优化这个问题。
时间复杂度：o(V⋅E)
// BellmanFord算法（参数与Dijkstra是一样的）
bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
// 一些初始化工作
size_t srci = GetVertexIndex(src);
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
dist[srci] = W();
pPath.resize(n, -1);
pPath[srci] = srci;
// 为了防止改变其中一条路径时候影响到其他路径
// 需要再次更新，总体最多更新n轮
for (size_t i = 0; i < n; ++i)
{
bool flag = false;
// 直接遍历判断是否需要松弛
for (size_t j = 0; j < n; ++j)
{
for (size_t k = 0; k < n; ++k)
{
if (_matrix[j][k] != MAX_W && dist[j] + _matrix[j][k] < dist[k])
{
dist[k] = dist[j] + _matrix[j][k];
pPath[k] = j;
flag = true;
}
}
}
// 若没有更新路径，那么说明不会再有影响了，直接break
if (flag == false)
break;
}
// 判断一下是否有负权回路
for (size_t j = 0; j < n; ++j)
{
for (size_t k = 0; k < n; ++k)
{
// 若还是有更新，说明有负权回路
if (_matrix[j][k] != MAX_W && dist[j] + _matrix[j][k] < dist[k])
{
return false;
}
}
}
return true;
} 测试用例：
void TestGraphBellmanFord()
{
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);
vector<int> dist;
vector<int> parentPath;
if (g.BellmanFord('s', dist, parentPath))
{
g.PrintShortPath('s', dist, parentPath);
}
else
{
cout << "存在负权回路" << endl;
}
}
运行结果：
s->y->7
s->y->x->t->z->-2
s->y->x->t->2
s->y->x->4 存在负权回路的测试用例：
void TestGraphBellmanFord()
{
//微调图结构，带有负权回路的测试
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', 'x', -3);
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;
}
}
运行结果：
存在负权回路Ⅲ. 多源最短路径 – Floyd-Warshall 弗洛伊德算法
1962 年弗洛伊德提出使用 动态规划 的思想来解决多源最短路径问题。
前面几种算法都是单源算法，计算指定起点到其他点的最短路径，即单源最短路径；而 Floyd 算法是多源最短路径算法，针对的是图中任意两点之间的最短路径。
并且 Floyd 算法 支持出现负权重的边，但是不支持出现负值环路。
所以 Floyd 算法本质是 三维动态规划，但是我们可以通过空间优化，优化掉最后一维度，变成二维的动态规划，最后即得到所以点的最短路径。
其中 dist[i][j] 表示从顶点 i 到顶点 j 的最短路径，而 path[i][j] 表示从顶点 i 到顶点 j 这条路径上到达顶点 j 的前一个顶点！
举个例子，v0->v2->v1->v3 中，则 path[0][3] 存储的是 1，也就是顶点 1。
- 时间复杂度：
O(V^3) - 空间复杂度：
O(V^2)
按我的理解来说该算法的思路，其实就是一个探查路径的过程。
比如现在有五个顶点，我们依次从 v1 到 v5 作为中介节点，假设我们以 v3->v2 的路径来讨论，则第一次就是探查是否从 v3->v1，再从 v1->v2，会比 v3 直接到 v2 更近，会的话就更新该新的路径！以此类推，接下来以 v2、v3、v4、v5 依次作为中介，看看比之前的距离更短，是的话就更新！
并且我们不断加入节点作为中介的过程中，其实就顺带判断了经过这些节点可能会产生的更短路径的可能。
如下图，比如说先以 v1 作为中介节点，此时打通了一条新路径：从 v2->v3 的新路径 v2->v1->v3，进行更新；接着加入 v2 作为新的中介节点时，也打通了一条新路径 v0->v2->v1->v3，侧面说明了加入中介节点判断的过程中其实中介节点也是作为可能的最短路径中的一份子！
上图中 D^(0) 表示还没更新时， D^(1) 表示的是 k = 0 的时候更新的状态，其他以此类推。（这里的 k 和下面代码中的 k 对应）
为什么下面的代码中要把 k 放到最外层循环呢？放到最里面那层不行吗？
k 放在里面的话，由于 i 和 j 就控制了行和列，所以是按每行每行来的 （去打印出每次变化的结果观察），那么每次去找中间节点的时候，有可能会出现一种情况，就是这一行可能是第一行或者比较前的行，那么下面那些行还没更新到，但是在前面的行找中间节点的最短路径的时候，可能要用到下面的一些行的路径去比较，由于下面的还没优化，就导致了上面的一些只能取到不是最优解。
所以 k 放在最里面的时候，只会每行每行去执行，那么这样子的话，前面执行完了，后面如果更新了更短的路径，前面的一些路径是没有得到优化的，这样子就错了。
而 k 放在最外面的话，意思是每次都是中间节点为 0 个开始，这样子找的话，每次 k 更新后都会从行首开始重新去更新，那么上面几行就会重新更新一遍，其实就和贝尔曼福特算法的最外层比较类似，总之就是为了防止后面改的路径影响到前面！
为什么 vvpPath[i][j] = vvpPath[k][j] 而不是 vvpPath[i][j] = k 呢？
以下图为例：
此时我们是轮流让 v0、v1、…… 作为中转节点，此时让 v1 作完中转节点后，路径长度表和上一节点下标表是这样子的：
此时让 v2 作为中转节点，在更新 v0->v3 的时候，发现可以通过 v2 生成一条路径 v0->v2->v1->v3，而此时 vvpPath[0][3] 中要存放的，其实是下标 1，也就是 v1，而不是当前的中转节点 k=2，疑惑解开了！
// Floyd-Warshall算法
void Floyd(vector<vector<W>>& vvdist, vector<vector<W>>& vvpPath)
{
// 初始化
size_t n = _vertexs.size();
vvdist.resize(n);
vvpPath.resize(n);
for (size_t i = 0; i < n; ++i)
{
vvdist[i].resize(n, MAX_W);
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] != MAX_W)
{
vvdist[i][j] = _matrix[i][j];
vvpPath[i][j] = i;
}
if (i == j)
{
vvdist[i][j] = 0;
vvpPath[i][j] = -1;
}
}
}
// 最核心的代码就只有这几行
for (size_t k = 0; k < n; ++k)
{
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
// i->k + k->j 如果小于 i->j 的距离则可以更新
if (vvdist[i][k] != MAX_W && vvdist[k][j] != MAX_W
&& vvdist[i][k] + vvdist[k][j] < vvdist[i][j])
{
vvdist[i][j] = vvdist[i][k] + vvdist[k][j]; // 状态方程
vvpPath[i][j] = vvpPath[k][j]; // 这个要理解清楚，因为可能连接j的不是k，而是其他的点
}
}
// 打印权值和路径矩阵观察数据
// for (size_t i = 0; i < n; ++i)
// {
// for (size_t j = 0; j < n; ++j)
// {
// if (vvdist[i][j] == MAX_W)
// {
// //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 TestFloydWarShall()
{
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.Floyd(vvDist, vvParentPath);
// 打印任意两点之间的最短路径
for (size_t i = 0; i < strlen(str); ++i)
{
g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);
cout << endl;
}
}
运行结果：
1->5->4->3->2 权值为：1
1->5->4->3 权值为：-3
1->5->4 权值为：2
1->5 权值为：-4
2->4->1 权值为：3
2->4->3 权值为：-4
2->4 权值为：1
2->4->1->5 权值为：-1
3->2->4->1 权值为：7
3->2 权值为：4
3->2->4 权值为：5
3->2->4->1->5 权值为：3
4->1 权值为：2
4->3->2 权值为：-1
4->3 权值为：-5
4->1->5 权值为：-2
5->4->1 权值为：8
5->4->3->2 权值为：5
5->4->3 权值为：1
5->4 权值为：6
腾讯云开发者
