DS图(下)(19)
文章目录
- 前言
- 一、最短路径的概念
- 二、单源最短路径-Dijkstra算法
- 三、单源最短路径-Bellman-Ford算法
- 四、多源最短路径-Floyd-Warshall算法
- 总结
前言
加油，今天就是图的最后一篇了，撑住！！
今天我们要学的就是最短路径问题！！
一、最短路径的概念
-
最短路径问题：从带权有向图中的某一顶点出发，找出一条通往另一顶点的最短路径，最短指的是路径各边的权值总和达到最小，最短路径可分为单源最短路径和多源最短路径。
-
单源最短路径指的是从图中某一顶点出发，找出通往其他所有顶点的最短路径，而多源最短路径指的是，找出图中任意两个顶点之间的最短路径。
二、单源最短路径-Dijkstra算法
有一个很重要的使用前提是：所有边的权值非负
Dijkstra算法的基本思想如下：
-
将图中的顶点分为两个集合，集合 S 中的顶点是已经确定从源顶点到该顶点的最短路径的顶点，集合 Q 中的顶点是尚未确定从源顶点到该顶点的最短路径的顶点。
-
每个顶点都有一个估计值，表示从源顶点到该顶点的可能最短路径长度，每次从集合 Q 中选出一个估计值最小的顶点，将其加入到集合 S 中，并对该顶点连接出去的顶点的估计值和前驱顶点进行松弛更新。
-
按照上述步骤不断从集合 Q 中选取估计值最小的顶点到集合 S 中，直到所有的顶点都被加入到集合 S 中，此时通过各个顶点的估计值就可以得知源顶点到该顶点的最短路径长度，通过各个顶点的前驱顶点就可以得知最短路径的走向。
Dijkstra算法的实现：
-
使用一个 dist 数组来记录从源顶点到各个顶点的最短路径长度估计值，初始时将源顶点的估计值设置为权值的缺省值（比如int就是0），表示从源顶点到源顶点的路径长度为0，将其余顶点的估计值设置为 MAX_W ，表示从源顶点暂时无法到达其他顶点。
-
使用一个 parentPath 数组来记录到达各个顶点路径的前驱顶点，初始时将各个顶点的前驱顶点初始化为 -1 ，表示各个顶点暂时只能自己到达自己，没有前驱顶点。
-
使用一个 bool 数组来记录各个顶点是否在 S 集合中，初始时所有顶点均不在 S 集合，表示各个顶点都还没有确定最短路径。
-
每次从 Q 集合中选出一个估计值最小的顶点 u，将其加入到 S 集合，并对顶点 u 连接出去的各个顶点 v 进行松弛更新，如果能够将顶点 v 更新出更小的估计值，则更新其估计值，并将被更新的顶点 v 的前驱顶点改为顶点 u ，因为从顶点 u 到顶点 v 能够得到更小的估计值，所以在当前看来（后续可能还会更新）到达顶点 v 的最短路径的前驱顶点就应该是顶点 u ，如果不能将顶点 v 更新出更小的估计值，则维持原样。
-
当所有的顶点都加入集合 S 后，dist 数组中存储的就是从源顶点到各个顶点的最短路径长度，parentPath 数组中存储的就是从源顶点到各个顶点的最短路径的前驱顶点，通过不断查找各个顶点的前驱顶点，最终就能得到从源顶点到各个顶点的最短路径。
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 (i != 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());
for (auto index : path)
{
cout << _vertexs[index] << "->";
}
cout << "权值和：" <<dist[i] << endl;
}
}
}
// 顶点个数是N -> 时间复杂度：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, MAX_W);
pPath.resize(n, -1);
dist[srci] = 0;
pPath[srci] = srci;
// 已经确定最短路径的顶点集合
vector<bool> S(n, false);
for (size_t j = 0; j < n; ++j)
{
// 选最短路径顶点且不在S更新其他路径
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];
}
}
S[u] = true;
// 松弛更新u连接顶点v srci->u + u->v < srci->v 更新
for (size_t v = 0; v < n; ++v)
{
if (S[v] == false && _matrix[u][v] != MAX_W
&& dist[u] + _matrix[u][v] < dist[v])
{
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
- 为了方便观察，可以在类中增加一个 PathprintShortPath 接口，用于根据 dist 和 parentPath 数组来打印最短路径及路径权值。
- 对于从源顶点 s 到目标顶点 j 的最短路径来说，如果最短路径经过了顶点 i ，那么最短路径中从源顶点 s 到顶点 i 的这条子路径一定是源顶点 s 到顶点 i 的最短路径，因此可以通过存储前驱顶点的方式来表示从源顶点到各个顶点的最短路径。
- Dijkstra算法每次需要选出一个顶点，并对其连接出去的顶点进行松弛更新，因此其时间复杂度是 O ( N^2 ) 空间复杂度是 O (N) 。
Dijkstra算法的原理
-
Dijkstra算法每次从集合 Q 中选出一个估计值最小的顶点 u ，将该顶点加入到集合 S 中，表示确定了从源顶点到顶点 u 的最短路径。
-
因为图中所有边的权值非负（使用Dijkstra算法的前提），所以对于估计值最小的顶点 u 来说，其估计值不可能再被其他比它估计值更大的顶点松弛更新得更小，因此顶点 u 的最短路径就是当前的估计值。
-
而对于集合 Q 中的其他顶点来说，这些顶点的估计值比顶点 u 的估计值大，因此顶点 u 可能将它们的估计值松弛更新得更小，所以顶点 u 在加入集合 S 后还需要尝试对其连接出去的顶点进行松弛更新。
三、单源最短路径-Bellman-Ford算法
跟前者相比可以处理负权的边，但是本质上是暴力求解，效率不如 Dijkstra
Bellman-Ford算法的基本思想如下：
-
Bellman-Ford算法本质是暴力求解，对于从源顶点 s 到目标顶点 j 的路径来说，如果存在从源顶点 s 到顶点 i 的路径，还存在一条从顶点 i 到顶点 j 的边，并且其权值之和小于当前从源顶点 s 到目标顶点 j 的路径长度，则可以对顶点 j 的估计值和前驱顶点进行松弛更新。
-
Bellman-Ford算法根据路径的终边来进行松弛更新，但是仅对图中的边进行一次遍历可能并不能正确更新出最短路径，最坏的情况下需要对图中的边进行 n−1 轮遍历（ n 表示图中的顶点个数）
Bellman-Ford算法的实现：
-
使用一个 dist 数组来记录从源顶点到各个顶点的最短路径长度估计值，初始时将源顶点的估计值设置为权值的缺省值（比如int就是0），表示从源顶点到源顶点的路径长度为0，将其余顶点的估计值设置为 MAX_W ，表示从源顶点暂时无法到达其他顶点。
-
使用一个 parentPath 数组来记录到达各个顶点路径的前驱顶点，初始时将各个顶点的前驱顶点初始化为 -1 ，表示各个顶点暂时只能自己到达自己，没有前驱顶点。
-
对图中的边进行 n−1 轮遍历，对于 i−>j 的边来说，如果存在 s−>i 的路径，并且 s−>i 的路径权值与边 i−>j 的权值之和小于当前 s−>j 的路径长度，则将顶点 j 的估计值进行更新，并将顶点 j 的前驱顶点改为顶点 i ，因为 i−>j 是图中的一条直接相连的边，在这条路径中顶点 j 的上一个顶点就是顶点 i 。
-
再对图中的边进行一次遍历，尝试进行松弛更新，如果还能更新则说明图中带有负权回路，无法找到最短路径。
// 时间复杂度：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, MAX_W);
// vector<int> pPath 记录 srci-其他顶点 最短路径父顶点数组
pPath.resize(n, -1);
// 先更新 srci -> srci 为缺省值
dist[srci] = W();
//cout << "更新边：i->j" << endl;
// 总体最多更新n轮
// 其实 n - 1 就行了
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)
{
// 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;
}
}
}
// 如果这个轮次中没有更新出更短路径，那么后续轮次就不需要再走了
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;
}
贝尔曼算法的原理
- 每一轮贝尔曼 - 福特算法会对图中的所有边进行一次松弛操作。在第一轮松弛操作中，算法可以找到从源点出发经过最多 1 条边到达各个顶点的最短路径；在第二轮松弛操作中，算法可以找到从源点出发经过最多 2 条边到达各个顶点的最短路径；以此类推。
- 由于任意两个顶点之间的最短路径最多包含 N - 1 条边，所以最多经过 N - 1 轮松弛操作，就可以找到从源点到各个顶点的最短路径。也就是说，在 N - 1 轮之后，所有顶点的最短路径估计值都不会再发生变化。
- 如果形成回路的各个边的权值之和为负数，则该回路为负权回路，找不到最短路径。
- 如果形成回路的各个边的权值之和为非负数，则多走这个回路是“徒劳”的，可能会使得路径长度变长
Bellman-Ford算法还有一个优化方案叫做SPFA（Shortest Path Faster Algorithm），就交给大家自行了解了
四、多源最短路径-Floyd-Warshall算法
Floyd-Warshall算法的基本思想如下：
-
Floyd-Warshall算法解决的是任意两点间的最短路径的算法，其考虑的是路径的中间顶点，对于从顶点 i 到顶点 j 的路径来说，如果存在从顶点 i 到顶点 k 的路径，还存在从顶点 k 到顶点 j 的路径，并且这两条路径的权值之和小于当前从顶点 i 到顶点 j 的路径长度，则可以对顶点 j 的估计值和前驱顶点进行松弛更新。
-
Floyd-Warshall算法本质是一个简单的动态规划，就是判断从顶点 i 到顶点 j 的这条路径是否经过顶点 k ，如果经过顶点 k 可以让这条路径的权值变得更小，则经过，否则则不经过。
Floyd-Warshall算法的实现：
-
使用一个 vvDist 二维数组来记录从各个源顶点到各个顶点的最短路径长度的估计值，vvDist[i][j] 表示从顶点 i 到顶点 j 的最短路径长度的估计值，初始时将二维数组中的值全部初始化为 MAX_W ，表示各个顶点之间暂时无法互通。
-
使用一个 vvParentPath 二维数组来记录从各个源顶点到达各个顶点路径的前驱顶点，初始时将二维数组中的值全部初始化为-1，表示各个顶点暂时只能自己到自己，没有前驱顶点。
-
根据邻接矩阵对 vvDist 和 vvParentPath 进行初始化，如果从顶点 i 到顶点 j 有直接相连的边，则将 vvDist[i][j] 初始化为这条边的权值，并将 vvParentPath[i][j] 初始化为 i ，表示在 i−>j 这条路径中顶点 j 前驱顶点是 i ，将 vvDist[i][i] 的值设置为权值的缺省值（比如int就是0），表示自己到自己的路径长度为0。
-
依次取各个顶点 k 作为 i−>j 路径的中间顶点，如果同时存在 i−>k 的路径和 k−>j 的路径，并且这两条路径的权值之和小于当前 i−>j 路径的权值，则更新 vvDist[i][j] 的值，并将 vvParentPath[i][j] 的值更新为 vvParentPath[k][j] 的值。
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];
}
}
}
}
Floyd-Warshall算法的时间复杂度是 O ( N^2 )，空间复杂度是 O ( N^2 ) 。虽然求解多源最短路径也可以以图中不同的顶点作为源顶点，去调用Dijkstra算法或Bellman-Ford算法，但Dijkstra算法不能解决带负权的图，Bellman-Ford算法调用 N 次的时间复杂度又太高
总结
结束了，感觉如何，难吧！！！
不用怀疑自己，我觉得这确实是最难的一部分，甚至比红黑树还难理解，因为它太抽象了