快乐的流畅：个人主页

个人专栏：《C游记》《进击的C++》《Linux迷航》

远方有一堆篝火，在为久候之人燃烧！

---

引言

前置知识：【数据结构】图的概念和存储结构

一、最短路径的概念

最短路径（shortest path）问题，指的是在有向图中，从某一顶点出发，找出通往另一顶点的边权值和最小的路径。

---

在正式开始介绍最短路径算法之前，我们需要先了解一个核心操作——边松弛（Edge Relaxation）。

首先，我们先说明，下图顶点中的值指的是该点到源点的距离。设S为源点，自身距离为0，而其他顶点未被遍历，内部为正无穷。

接下来，先遍历A点，则A点的值改为1，前驱结点为S。

其次，对点B进行同样操作，B点的值改为3，前驱结点为S。

最后，最关键的步骤来了，我们发现S->A->B比S->B路径更短（权值和更小），则将B点的值改为2，前驱结点改为A。

而最后这一步，就叫做边松弛，简称松弛。通过松弛操作，我们可以降低到达某点的距离（即为路径的权值和）。不断地进行松弛操作，最终我们便可以得到源点到所有点的最短距离。

二、Dijkstra算法

2.1 思想

Dijkstra算法是一种贪心算法：

1. 每次先选出离源点距离最近的点，并纳入集合（表示该点的最短路径已确定）。
2. 再对该点周围的边进行松弛。

由于 Dijkstra 算法假设一旦处理了某个节点，它的最短路径就已经确定，所以该算法不能处理带负权边的图。

2.2 实现

void Dijkstra(const V& src, vector<W>& dist, vector<int>& prev)
{int n = _vertexs.size();dist.resize(n, W_MAX);prev.resize(n, -1);vector<bool> S(n, false);int srci = GetIndex(src);dist[srci] = W();prev[srci] = srci;//<与源点的距离,目标点下标>priority_queue<pair<W, int>, vector<pair<W, int>>, greater<pair<W, int>>> minHeap;minHeap.push({ dist[srci],srci });while (!minHeap.empty()){//找到距离srci最近的点uauto top = minHeap.top();minHeap.pop();int u = top.second;S[u] = true;//对点u周围的边进行松弛for (int i = 0; i < n; ++i){if (!S[i] && _edges[u][i] != W_MAX&& dist[u] + _edges[u][i] < dist[i]){dist[i] = dist[u] + _edges[u][i];prev[i] = u;minHeap.push({ dist[i],i });}}}
}

三、Bellman-Ford算法

3.1 思想

Bellman-Ford算法是一种基于动态规划的算法，不依赖贪心策略：

• 对每条边进行松弛操作，共进行n-1次（n为顶点数量），每次迭代尝试松弛所有边。

ps：每一轮松弛时，不关注哪个节点已经处理，而是尝试通过所有边更新每个节点的距离。

Bellman-Ford 的松弛次序是全局的、重复的，它会反复松弛直到达到稳定状态，因此可以应对负权边的情况。

3.2 实现

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& prev)
{int n = _vertexs.size();dist.resize(n, W_MAX);prev.resize(n, -1);int srci = GetIndex(src);dist[srci] = W();prev[srci] = srci;//每对所有边进行一次松弛，已确定的最短路径的边数加一（往外扩大一圈）for (int k = 0; k < n - 1; ++k){bool update = false;for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (_edges[i][j] != W_MAX&& dist[i] + _edges[i][j] < dist[j]){dist[j] = dist[i] + _edges[i][j];prev[j] = i;update = true;}}}if (!update){break;}}//检测是否存在负权环路for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (_edges[i][j] != W_MAX&& dist[i] + _edges[i][j] < dist[j]){return false;}}}return true;
}

四、Floyd-Warshall算法

4.1 思想

相比于前两个算法，Floyd-Warshall算法并不是基于单一源点的算法，而是直接计算图中所有点对之间的最短路径。

Floyd-Warshall算法是一个典型的动态规划算法：

1. 依次遍历每个节点 k ，将它作为中间节点。
2. 对于每一对节点 (i, j) ，检查是否通过节点k 能获得更短的路径。如果是，则松弛点对 (i, j) 的距离。

4.2 实现

void FloydWarshall(vector<vector<W>>& dist, vector<vector<int>>& prev)
{int n = _vertexs.size();dist.resize(n, vector<W>(n, W_MAX));prev.resize(n, vector<int>(n, -1));for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (_edges[i][j] != W_MAX){dist[i][j] = _edges[i][j];prev[i][j] = i;}else if (i == j){dist[i][j] = 0;}}}//通过迭代优化，将三维动态规划转为二维for (int k = 0; k < n; ++k){for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){if (dist[i][k] != W_MAX && dist[k][j] != W_MAX&& dist[i][k] + dist[k][j] < dist[i][j]){dist[i][j] = dist[i][k] + dist[k][j];prev[i][j] = prev[k][j];}}}}
}

五、Dijkstra、Bellman-Ford和Floyd-Warshall的对比

5.1 适用场景

• Dijkstra：

  • 用途：单源最短路径算法，适用于无负权边的图。
  • 应用场景：适用于网络路由、地图导航等无负权图中的路径计算。

• Bellman-Ford：

  • 用途：单源最短路径算法，适用于有负权边的图。
  • 应用场景：适用于可能包含负权边的图，如金融系统中带有成本和收益的网络建模，或负值边表示优惠或折扣的情况。

• Floyd-Warshall：

  • 用途：多源最短路径算法，计算任意两点之间的最短路径。
  • 应用场景：适用于所有点对的路径问题，如社交网络中两个人之间最短交友路径的计算、全连接网络拓扑分析等。

5.2 时间复杂度

• Dijkstra：

  • 使用二叉堆实现的优先队列：O(E + V log V)（其中 E 是边数，V 是顶点数）。
  • 适合稠密图。

• Bellman-Ford：

  • 时间复杂度：O(VE)。
  • 由于每次松弛需要遍历所有边，因此在稀疏图中较为高效。

• Floyd-Warshall：

  • 时间复杂度：O(V^3)。
  • 适合小型图或稠密图，节点较少但需要计算所有点对的最短路径。

5.3 松弛次序

• Dijkstra：

  • 贪心策略：每次选取当前未处理的距离最小的节点进行松弛。
  • 松弛顺序：先处理距离已知最短的节点，再依次更新它的邻居节点的距离，一旦处理一个节点，它的最短路径即确定。

• Bellman-Ford：

  • 全局松弛策略：松弛所有边 V-1 次。
  • 松弛顺序：每一轮松弛所有边，通过反复更新保证所有节点距离都正确。允许负权边。

• Floyd-Warshall：

  • 基于中间节点的松弛策略：通过每个节点 k 作为中间节点，尝试更新所有点对之间的距离。
  • 松弛顺序：每次引入一个新的中间节点 k，尝试通过 i->k->j 的路径更新任意两点 (i, j) 之间的最短距离。

5.4 处理负权边与负权环

• Dijkstra：

  • 不支持负权边：如果图中存在负权边，Dijkstra 的贪心策略将导致错误的结果。
  • 原因：一旦某个节点的最短路径被确定，Dijkstra 不会再更新这个节点，但负权边可能在后续引入更短的路径。

• Bellman-Ford：

  • 支持负权边，可以正确计算负权边的最短路径。
  • 负权环检测：算法通过 V-1 次松弛操作后检查是否仍有边可以被松弛。如果存在，则说明图中有负权环，报告错误。

• Floyd-Warshall：

  • 支持负权边，可以计算负权边的最短路径。
  • 负权环检测：通过检查矩阵的对角线元素，如果某个顶点的距离对角元素被更新为负值，则说明图中存在负权环。

5.5 总结表格

算法	适用场景	时间复杂度	松弛次序	负权边支持	负权环检测
Dijkstra	单源最短路径，适用于无负权图	O(E + Vlog V)	贪心选择距离最短的节点，逐步松弛	不支持	不支持
Bellman-Ford	单源最短路径，适用于有负权边的图	O(VE)	反复松弛所有边 V-1 次	支持	支持
Floyd-Warshall	多源最短路径，适用于小图或全图求解	O(V^3)	通过中间节点逐步松弛所有点对	支持	支持

5.6 选择算法的依据

• 如果需要从单个源节点计算最短路径，并且图中没有负权边，Dijkstra 是最优选择，因其效率较高。
• 如果图中有负权边，并且需要从单个源节点计算最短路径，则应使用 Bellman-Ford，它能够处理负权边并检测负权环。
• 如果需要计算图中所有点对的最短路径（例如全连接图），Floyd-Warshall 是合适的选择，尽管它的时间复杂度较高，但处理小规模图时效果较好。

真诚点赞，手有余香