C++--数据结构--最短路径--Dijkstra--Bellman-Ford算法--Floyd-Warshall算法--高阶0713 14
注：本篇所用的某些未在本文中实现的函数，或不明确的类，均在上篇博客中有详细过程，因篇幅问题不再赘述。
C++--数据结构--图的相关概念及模拟实现--高阶0712_Gaze！的博客-CSDN博客
1. Dijkstra算法
Dijkstra算法需要开辟两个数组，vector<W>dist 和 vector<int>pPath。
dist存放当前所选定的顶点到其他顶点的距离
pPath存放的是从哪个节点来的，存的是该节点的下标
思路：
将全部顶点分为两个集合S和Q，S是已经确定了最短路径的集合，初始时为空即可。假设进行Dijkstra算法的起始顶点是src，其映射下标是srci,将dist[srci]=0。
每次选取路径最小的，即dist数组内最小的那个值，将dist下标（路径终点顶点）纳入S集合，用该节点再次更新dist数组
1.1 Dijkstra代码
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);
pPath.resize(n, -1);
//将起始顶点到自己的距离置零
dist[srci] = 0;
pPath[srci] = srci;
//S集合 一开始全部未使用
vector<bool> S(n, false);
for (size_t j = 0; j < n; j++)
{
int u = 0;
W min = MAX_W;
for (size_t i = 0; i < n; i++)
{
if (S[i] == false && dist[i] < min)
{
u = i;
min = dist[i];
}
}
//srci->u是最小的边 根据Dijkstra算法 我们把u纳入使用列表
S[u] = true;
//用u来尝试更新dist数组
for (size_t t = 0; t < n; t++)
{
if (S[t] == false && _matrix[u][t]!=MAX_W
&& dist[u] + _matrix[u][t] < dist[t])
{
//从srci到t的权重 大于 从srci到u再从u到t 更新
dist[t] = dist[u] + _matrix[u][t];
pPath[t] = u;//t这个点是从u过来的
}
}
}
}注意是实现在Graph类中的
1.2PrintShortPath函数
在经过Dijkstra算法后的pPath数组是倒着记录路径的，为了方便观察，我们通过一个函数使结果更易观察。
void PrintShortPath(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 (srci != i)
{
int parenti = i;//不能改变i 因为要以i为判据进行循环
vector<int>path;
//所有顶点的起点都是srci 不是就继续找父顶点
while (parenti!= srci)
{
path.push_back(parenti);
parenti = pPath[parenti];
}
//现在父节点就是srci了
path.push_back(srci);
reverse(path.begin(), path.end());
for (auto& e : path)
{
cout << _vertexs[e] << "->";
}
cout << dist[i] << endl;
}
}
}1.3测试代码及结果
注意：Dijkstra无法适用于含有负权边的情况，本质上是贪心思想。负权的介入会影响结果。
2.Bellman-Ford
bellman-ford算法可以解决负权图，但bellman-ford是一种暴力求解的算法，如果是邻接矩阵实现的图才有这种算法，时间复杂度为O(N^3)比Dijkstra算法O(N^2)高。
思路：
其实就是一种暴力遍历。
for (size_t j = 0; j < n; ++j)
{
// srci -> i + i ->j
if (_matrix[i][j] != MAX_W && 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;
}
}
由于是按照顶点的顺序遍历的，当遇到负权的时候，可能会改变路径，但是在此之前的顶点已经按照未改变的路径更新的权值，会造成权值和路径对不上的问题。如下图，syztx的映射为01234，
以s为起始更新,st的权值为6，直到我遍历到i为4（即以x开始更新），此次遍历，让从s->t出现了另一条权值更小的路径(s->y->x->t),但在遍历x之前，s->z的路径是从s->t->z来的，那么s->z本应具有更小的权值，却因为顺序而没有得到调整。
所以我们要进行三次循环遍历。因为新更新路径可能又会影响其他路径，所以还需要继续更新，最多更新n轮。
2.1代码
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);
pPath.resize(n, -1);
dist[srci] = 0;// 或者W()更准确
pPath[srci] = srci;//一定要加不然调用PrintShortPath会死循环的
for (size_t k = 0; k < n; k++)
{
bool update = false;
cout << "更新第" << k + 1 << "轮" << endl;
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
if (_matrix[i][j] != MAX_W && 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] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
{
return false;
}
}
}
return true;
}2.2测试代码及运行结果
有一个非常奇怪的问题就是我换了个起始节点不是s了，改成'y'就会出现所有路径都是接近INT_MIN的情况。希望有大佬点一点。
3.Floyd-Warshall算法
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。
Floyd算法考虑的是一条最短路径的中间节点，即简单路径p={v1,v2,…,vn}上除v1和vn的任意节点，设k是p的一个中间节点，那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1，p2。p1 是从i到k且中间节点属于{1，2，…，k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1， 2，…，k-1}取得的一条最短路径。
3.1代码
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, 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] = 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的路径
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];
// 找跟j相连的上一个邻接顶点
// 如果k->j 直接相连，上一个点就k，vvpPath[k][j]存就是k
// 如果k->j 没有直接相连，k->...->x->j，vvpPath[k][j]存就是x
vvpPath[i][j] = vvpPath[k][j];
}
}
}
// 打印权值和路径矩阵观察数据
//方便Debug 可以不写
for (size_t i = 0; i < n; ++i)
{
for (size_t j = 0; j < n; ++j)
{
if (vvDist[i][j] == MAX_W)
{
printf("%3c", '*');
}
else
{
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)
{
printf("%3d", vvpPath[i][j]);
}
cout << endl;
}
cout << "=================================" << endl;
}
}3.2测试代码及结果
