慕斯主页：修仙—别有洞天
♈️今日夜电波：アンビバレント—Uru
0:24━━━━━━️──────── 4:02 ◀️ ⏸ ▶️ ☰
关注点赞收藏您的每一次鼓励都是对我莫大的支持
什么是最短路径？
最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小 即路径上各边权值之和最小的路径。以下是关于最短路径问题的一些关键信息：
Dijkstra算法：这是一种广泛使用的算法，用于在非负权重的图中找到一个顶点到其他所有顶点的最短路径。它使用贪心策略，每次从未访问的顶点中选择一个距离起点最近的顶点，并更新其他顶点到起点的距离。需要注意的是，Dijkstra算法不能处理带有负权重边的图。Bellman-Ford算法：这是另一种算法，它可以处理带有负权重边的图。该算法通过对所有的边进行V-1次松弛操作来找到最短路径，其中V是图中顶点的数量。如果图中存在负权重环，则算法会报告这一情况。Floyd-Warshall算法：这是一种动态规划算法，它可以计算图中任意两点之间的最短路径。该算法的时间复杂度较高，为O(V^3)，但它可以处理包含负权重边的图，只要没有负权重环。最短路径的性质：最短路径具有最优子结构的性质，即从起点到任一点的最短路径上的任何子路径也是最短的。这一性质是Dijkstra算法和大多数最短路径算法的基础。
Dijkstra算法
如何理解Dijkstra算法？
Dijkstra算法（迪杰斯特拉算法）是一种非常著名的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。这个算法采用了贪心策略，每次迭代中都会选择当前未处理节点中距离起始点最近的节点，然后更新该节点的所有邻居节点的距离值。
以下是Dijkstra算法的基本步骤：
初始化：将起始节点的距离设为0，其他所有节点的距离设为无穷大（表示当前还无法到达这些节点）。同时，创建一个已处理节点集合和一个未处理节点集合，起始节点放入已处理节点集合，其他节点放入未处理节点集合。选择节点：从未处理的节点集合中选择一个距离起始点最近的节点，将其加入已处理节点集合。更新邻居：对于刚刚选出的节点的每一个邻居节点，如果通过当前节点到达该邻居节点的距离比之前记录的距离更短，则更新该邻居节点的距离值。重复：重复步骤2和步骤3，直到所有节点都已经被处理。
在算法的实现过程中，通常会使用优先队列（例如最小堆）来优化选择节点的步骤，使得每次都能快速找到未处理节点中距离起始点最近的节点。
需要注意的是，Dijkstra算法不能处理带有负权重的边的情况。如果图中存在负权重的边，那么算法可能无法正确计算出最短路径。此外，虽然Dijkstra算法可以处理带有权重的图，但它不能处理存在环的情况，特别是当环的权重之和为负时。
总的来说，Dijkstra算法是一种非常有效的单源最短路径算法，其思想直观且易于理解，是图论和计算机科学中的基础知识之一。
Dijkstra算法的实现
Dijkstra算法还是基于邻接矩阵上实现的。对于函数的接口，我们是通过给定的顶点来确定从谁开始到其他顶点的最短路径的，还需要额外传递两个参数dist存储到各顶点的最短路径，pPath存储他们的父亲节点。接下来我们一步一步的实现：（1）初始化，获得对应顶点的下标，初始化dist和pPath，需要注意其中源顶点到源顶点的值即为0，源顶点的父亲即为源顶点，再定义一个已经确定最短路径的顶点S集合用于后续的操作。（2）开始遍历，我们需要找到n个顶点的最小路径，所以需要进行n次循环。（3）每次循环都需要定义两个变量，u用于存储S中没确定最短路径的顶点，min则用于选出现在顶点到u最短的边。（4）u被选出来，说明u是相邻最小的边的顶点了，因此我们可以将S中u的位置至为true，表示已径确定最小路径的顶点。（5）后续在u被选出来后，我们需要根据u来更新源顶点通过u到另外顶点的最短距离，松弛更新u连接顶点v。（6）同样是一个循环，遍历u->v中的v这个顶点，我们可以通过_matrix[u][v] != MAX_W来判断u是否可以到v来筛选v，再通过S[v] == false来确定v并没有被选出最短路径，最后根据 dist[u] + _matrix[u][v] < dist[v] 来判断是否松弛更新u连接顶点v。（7）最后符合条件则更新v在dist中的值，以及更新v的父节点u在pPath中。具体实现如下：
void Dijkstra(const V& src, vector
{
size_t srci = GetVertexIndex(src);//获取对应顶点的下标映射
size_t n = _vertexs.size();
dist.resize(n, MAX_W);
pPath.resize(n, -1);
dist[srci] = 0;//源顶点到源顶点的值即为0
pPath[srci] = srci;//源顶点的父亲即为源顶点
// 已经确定最短路径的顶点集合
vector
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)//S[i]还没有被选过且找到最小的边
{
u = i;//u是不在S中的点
min = dist[i];
}
}
//u被选出来，说明u是相邻最小的边的顶点了
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])//v表示u连接出去边的顶点
{
dist[v] = dist[u] + _matrix[u][v];
pPath[v] = u;
}
}
}
}
Bellman-Ford算法
如何理解Bellman-Ford算法？
Bellman-Ford算法是一种用于解决单源最短路径问题的算法，特别是在图中包含负权边的情况下。
Bellman-Ford算法的核心思想是“松弛操作”，通过不断迭代来更新最短路径的估计值。这个算法可以处理存在负权边的图，解决了Dijkstra算法无法处理负权边的问题。Bellman-Ford算法通过m次迭代来确定从源点到终点不超过m条边构成的最短路径。在没有负环的情况下，这个算法能够找到正确的最短路径。然而，如果图中存在负环，算法也能检测到这一点。
具体来说，Bellman-Ford算法的工作原理如下：
初始化：将所有节点的最短路径估计值初始化为无穷大，除了源点自身的估计值为0。迭代：对于图中的每一条边，尝试通过该边进行松弛操作，即如果通过这条边能够得到一个更小的最短路径估计值，就更新这个估计值。需要注意的是：如果我们在更新完一个顶点的边后，如果通过该顶点的边可以让前面的边更小，但是我们的更新已经完成了，那么这样就出错了！因此，可以通过让整个已经完整迭代过的最小生成树再次进行迭代（迭代多少次呢？如果每次迭代都出现上述的情况，那么最多就是n次！）因此他的时间复杂度是比较高的：O(N^3)检测负环：如果在迭代完成后，再次进行迭代仍然可以进行松弛操作，那么图中必然存在负环。
Bellman-Ford算法的实现
Bellman-Ford算法也是基于邻接矩阵的基础上实现的。还是通过传递一个源顶点来确定从谁开始到其他顶点的最短路径的，还需要额外传递两个参数dist存储到各顶点的最短路径，pPath存储他们的父亲节点。接下来我们一步一步的实现：（1）初始化，更新dist 记录srci-其他顶点最短路径权值数组、pPath 记录srci-其他顶点最短路径父顶点数组，最后更新dist中传入的源顶点的位置未缺省值（实际上就是0）。（2）按照上述的原理，我们要对图中的每一条边都尝试通过该边进行松弛操作，这就体现到邻接矩阵的优势所在了。只需要两个for循环即可遍历所有的边。我们在之前的文章对邻接矩阵中不能连接到的边做了将他置为MAX_W的处理，因此根据该条件即可知道是否可以由i直接连接到j，需要注意的是：如果说Dijkstra贪心的是第一条边，那么Bellman-Ford算法的思想实际上是贪心的最后的一条边。我们只需要根据是否可以用更小的权值到达目标边即可。（为什么可以这么做？因目标顶点的最近顶点的dist非MAX_W就说明了从原顶点一定是可以到达最近顶点的，而现在你现在合起来的权值有比原来的小，这就是说明是一种更好的路径！）如下写出初步代码：
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])
{
dist[j] = dist[i] + _matrix[i][j];
pPath[j] = i;
}
}
}
（3）为什么说是初步代码呢？这是因为上面原理提到的后续的更新完了，后面的更新可以使前面的路径更小！因此我们需要让他们再次更新！（最多跟新n次！即每次更新都会造成新的更短的路径！）如果更新了n次后还存在更新操作，那么就是带负权的回路！具体实现如下：
// 空间复杂度：O（N）
bool BellmanFord(const V& src, vector
{
size_t n = _vertexs.size();
size_t srci = GetVertexIndex(src);
// vector
dist.resize(n, MAX_W);
// vector
pPath.resize(n, -1);
// 先更新srci->srci为缺省值
dist[srci] = W();
// 总体最多更新n轮
for (size_t k = 0; k < n; ++k)
{
// i->j 更新松弛
bool update = false;
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;
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;
}
FloydWarshall算法
如何理解FloydWarshall？
Floyd-Warshall算法是一种计算图中所有顶点对之间最短路径的动态规划算法。
该算法的核心思想是逐步更新两个顶点之间的最短路径，直至包含所有其他顶点作为中间顶点为止。这样，通过不断添加中间顶点来更新最短路径，最终得到的结果就是所有顶点对之间的最短路径。
具体来说，Floyd-Warshall算法的工作原理如下：
初始化：将图的邻接矩阵作为初始距离矩阵，如果两个顶点之间没有直接相连的边，则距离设为无穷大。迭代更新：使用动态规划的思想，逐步考虑所有可能的中间顶点。对于每一对顶点(u, v)，检查是否存在一个中间顶点w，使得从u到w再到v的距离比当前记录的u到v的距离更短。如果是，则更新u到v的最短距离。结果：经过n次迭代后，其中n为图中顶点的数量，得到的矩阵即为所有顶点对之间的最短路径。
总的来说，Floyd-Warshall算法在解决无向图中的最短路径问题时非常有效，特别是当需要找到所有顶点对之间的最短路径时。然而，它的时间复杂度较高，为O(n^3)，因此在处理大型图时可能不是最优选择。此外，该算法不能处理带有负权重边的图，因为可能存在负权重环导致的无限递减问题。
FloydWarshall算法的实现
FloydWarshall算法也是基于邻接矩阵的基础上实现的。可以看到三大最短路径以及最小生成树的算法都通过邻接矩阵来实现的，这也说明了邻接矩阵的高效，当然有些算法也是可以使用的邻接表实现的。FloydWarshall算法传入两个二维的矩阵vvDist和vvpPath，分别用于存储权值以及路径，这很明显的就是一个二维dp的运用。接下来我们一步一步的实现：（1）初始化，初始化vvDist距离设为无穷大和vvpPath路径设为-1，接着更新直接相连的边。（2）本算法的状态表示为 D[i][j][k]表示从点i到点j只经过0到k个点最短路径 。以及状态转移方程为：
（3）按照上述的原理我们以最短路径的更新i-> {其他顶点} ->j。在这里，我们让第一层循环k作为的中间点尝试去更新i->j的路径（因为所有点都可以成为中间点包括他自己、目标点），需要注意的是：再次强调本算法是将更新所有顶点到所有顶点的最短路径！因此我们需要两层循环：一层i表示源顶点，一层j表示目标顶点。（4）由于上面初始化的时候已经将不经过k的情况都初始化完成了，那么我们直接判断经过k的时候是否比不经过k小即可，但是需要注意前提是：i到k和k到j是存在对应的边的。而父路径下标的存储的是j上一个顶点，这个顶点是带商讨的，因此这也是为什么我们用二维矩阵的原因，因为他也同步更新的！也就是要存vvpPath[k][j]。需要具体实现如下：
void FloydWarshall(vector
{
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];
}
}
}
}
}
感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
给个三连再走嘛~
参考文章
您阅读本篇文章共花了：
发表评论