图的最短路径算法：Dijkstra、Floyd-Warshall、Bellman-Ford

本文意在探讨图中最短路径算法 Dijkstra、Floyd-Warshall、Bellman-Ford 的对比和细节

整体分为如下四部分

0. 总结性的比较了 Dijkstra、Floyd-Warshall、Bellman-Ford
1. Dijkstra 算法介绍
2. Floyd-Warshall 算法介绍
3. Bellman-Ford 算法介绍

其中1、2、3 算法介绍部分会比较简洁，整体而言 Dijkstra 算法相对来说较难理解，而 Floyd-Warshall、Bellman-Ford 通过伪代码可以快速理解其含义

建议可以先快速浏览 0，然后看 2、3、1，再阅读一次 0

0 最短路径中：Dijkstra、Floyd-Warshall、Bellman-Ford 算法比较的 Cheat Sheet

比较维度	Dijkstra	Floyd-Warshall	Bellman-Ford
最佳用途	寻找地图上点到点的最短路	计算网络中所有点对的最短路	路径规划/网络优化，尤其是存在负权边时
目标	单源最短路径	所有节点对的最短路径	单源最短路径
时间复杂度	O(V^2) 或 O(E + V log V)	O(V^3)	O(VE)
空间复杂度	O(V)	O(V^2)	O(V)
负权边	不支持（仅正权边）	支持（但不支持负权环）	支持（且能检测负权环）
底层数据结构	优先队列/堆	二维数组	数组
是否适用于分布式	否	否	是
算法类型	贪心算法	动态规划	动态规划
实现难度	中等	简单	简单
更新策略	单点更新	全局更新	单点更新
路径重构	直接通过前置节点	通过中间节点递归构建	直接通过前置节点

0.A 关于上面表格的问题 1

“是否适用于分布式” 是什么含义

0.A 问题 1 的回答

在这里，“是否适用于分布式”指的是算法是否能够被有效地实施在一个分布式计算环境中，也就是多个计算节点分别进行计算的情况。

对于分布式环境，算法能否被分解成可以在网络中不同节点上独立运行的子过程是一个重要的考量。在这样的环境中，节点通常只拥有局部的信息，而不是整个网络的全局信息，并且需要通过消息传递来协调解决方案。

例如，Bellman-Ford算法可以被用在分布式系统中，每个节点可以独立地运行算法的一部分，并通过网络与其他节点交换信息。这个特性使其适用于如路由协议之类的分布式网络应用，如RIP（Routing Information Protocol）。

相比之下，Dijkstra算法和Floyd-Warshall算法通常在一个单一的计算实体上执行，并需要有关全局网络的全部信息，所以它们在标准形式下不适用于分布式环境。然而，Dijkstra算法也有可能被修改为一个分布式版本，如在OSPF（Open Shortest Path First）路由协议中使用的那样。

0.B 关于上面表格的问题 2

Floyd-Warshall、Bellman-Ford 这两个算法是基于动态规划

我的知识储备中，动态规划需要满足最优子结构和重叠子问题两个特征，这两个算法是如何满足动态规划特性的

0.B 问题 2 的回答

Floyd-Warshall算法和Bellman-Ford算法确实是基于动态规划思想设计的，下面解释它们是如何满足动态规划特性的：

• Floyd-Warshall算法
  • 最优子结构：Floyd-Warshall算法的最优子结构体现在计算任意两点i和j之间的最短路径时，可以通过包含中间节点k的子路径来实现。如果已知从i到k和从k到j的最短路径，那么可以通过它们来构建从i到j的最短路径。算法本质上是在尝试通过加入更多的中间节点来不断更新两点之间的最短路径。
  • 重叠子问题：在计算节点对之间的最短路径时，算法重复解决了许多相同的子问题。例如，在计算从i到j的最短路径时，需要用到从i到其他所有节点以及从所有节点到j的最短路径信息，而这些信息在计算其他节点对之间的最短路径时会重复使用。
• Bellman-Ford算法
  • 最优子结构：Bellman-Ford算法利用的最优子结构是指从源点到目标点的最短路径可以通过一系列的最短路径决策来构建。如果已知从源点到节点u的最短路径，并且存在一条边从u到v，那么只有当从源点经u到v的路径比已知的从源点到v的路径更短时，才更新源点到v的距离。
  • 重叠子问题：在更新节点间最短路径的过程中，算法会在每次迭代中对所有边进行松弛操作。每次更新一个节点的最短路径估计时，都可能用到其他节点的最短路径估计，这些估计在算法的多个迭代中被重复计算和使用。

在这两个算法中，动态规划的思想通过构建表格（在Floyd-Warshall算法中是一个二维表格，而在Bellman-Ford算法中通常是一维数组）来保存子问题的解决方案，并通过这些已解决的子问题来解决更大的问题。这些表格存储了算法的中间结果，使得每个子问题只需要计算一次，从而避免了重复计算。

1. Dijkstra 算法

算法概览：在图中找到从源点到其他所有点的最短路径，通过为每个顶点维护一个最短路径估计，并逐渐更新这些估计，直到找到最短路径。

伪代码

function Dijkstra(Graph, source):dist[source] ← 0                           // 初始化源点到自己的距离为0for each vertex v in Graph:                 // 对图中每个顶点if v ≠ sourcedist[v] ← ∞                         // 初始化源点到每个顶点的距离为无穷大prev[v] ← undefined                     // 前置节点初始化为未定义Q ← the set of all nodes in Graph           // 将所有节点加入队列while Q is not empty:                       // 当队列非空时循环u ← vertex in Q with min dist[u]        // 从Q中找出距离最小的顶点uremove u from Q                         // 从Q中移除顶点ufor each neighbor v of u:               // 遍历u的所有邻居alt ← dist[u] + length(u, v)        // 计算经u到邻居v的距离if alt < dist[v]:                   // 如果经u到v的距离更短dist[v] ← alt                   // 更新距离prev[v] ← u                     // 更新前置节点为ureturn dist, prev                           // 返回所有节点的最短距离以及路径

在此伪代码中，Graph 表示图，source 表示源点，dist 表示从源点到每个顶点的距离，prev用来记录最短路径上的前置节点。Q 是一个优先队列，用来找出当前未处理的最近的顶点。length(u, v) 是边 (u, v) 的权重。这个算法假设图中所有边的权重都是非负的。

2. Floyd-Warshall算法

算法概览：核心思想是通过迭代过程，考虑将所有其他顶点作为中间顶点来更新每对顶点之间的最短路径

伪代码

function FloydWarshall(W)n := length(W) // W is the graph represented as an adjacency matrixD := W        // D is a distance matrix that will be updatedfor k from 1 to nfor i from 1 to nfor j from 1 to nif D[i][k] + D[k][j] < D[i][j] thenD[i][j] := D[i][k] + D[k][j]return D

在这里，W 是一个邻接矩阵，表示图中所有顶点之间的权重（或距离）。如果不存在直接的边，那么W[i][j] 应该是一个非常大的数（代表无穷）。D 是 Floyd-Warshall 算法计算过程中的距离矩阵，最后会变成所有顶点对之间最短路径的长度。在伪代码中，n 是顶点的数目。

疑问

算法中的 i j k 循环顺序可以调整吗

解答

Floyd-Warshall 算法中的三个循环 (i, j, k) 的顺序是可以互换的，但通常 k 循环是放在最外层的。在算法的迭代过程中，k 循环代表的是允许作为中介点的顶点集合的逐步扩大。换句话说，算法首先计算只允许使用顶点 1 作为中介的所有最短路径，然后是顶点 1 和 2，依此类推，直到考虑所有顶点作为中介点。

将 k 循环放在最外层确保了在更新 D[i][j] 时，考虑的所有中间顶点都是在之前的迭代中已经处理过的。如果 i 和 j 循环在 k 循环的外面，算法就不能保证这一点，可能会导致不正确的结果。

因此，k 循环必须保持在最外层，而 i 和 j 循环的顺序可以互换，因为它们只是在独立地更新两点之间的最短距离。

3. Bellman-Ford 算法

算法概览：通过对图中所有边进行重复松弛操作，以计算图中单个源点到其他所有点的最短路径，能够处理包含负权边的图。

伪代码

function BellmanFord(vertices, edges, source):// 初始化距离数组，将源点到所有点的距离设为无穷大，除了源点自身设为0distance := array of size |vertices|, fill with ∞ (infinity)distance[source] := 0// 循环|V|-1次，V是顶点数量for i from 1 to |vertices|-1:// 对每条边进行一次松弛操作for each edge (u, v, w) in edges:if distance[u] + w < distance[v]:distance[v] := distance[u] + w// 检测负权重循环// 再次对所有边进行检查，如果还能找到更短的路径，则存在负权重循环for each edge (u, v, w) in edges:if distance[u] + w < distance[v]:// 如果这里的条件为真，则图中存在从源点可达的负权重循环return "Graph contains a negative-weight cycle"return distance

疑问 1

for i from 1 to |vertices|-1:// 对每条边进行一次松弛操作for each edge (u, v, w) in edges:
...

这里的 (u, v, w) 和外层循环 for i from 1 to |vertices|-1 有什么关系吗

u, v 需要是外层顶点循环中的一个吗

疑问 1 的回答

在贝尔曼-福特算法的伪代码中，(u, v, w) 表示一条边，其中 u 是起点，v 是终点，w 是这条边的权重。

这些边和外层顶点循环 for i from 1 to |vertices|-1 并没有直接的对应关系，也就是说，u 和 v 不需要是外层顶点循环中的特定顶点。

外层的循环 for i from 1 to |vertices|-1 的目的是重复尝试“松弛”操作足够多的次数，确保算法能正确处理所有的最短路径，即使这些路径可能通过多个顶点。在无负权重循环的情况下，任何最短路径最多包含 |vertices|-1 条边。因此，重复进行 |vertices|-1 次遍历所有边并尝试进行松弛操作，足以保证算法找到所有可能的最短路径。

内层循环 for each edge (u, v, w) in edges 则是负责实际的松弛操作，它会检查图中的每一条边，无论这些边的起点和终点是什么。每次内层循环时，算法会尝试更新从起点 u 到终点 v 的最短路径估计。

简而言之，外层循环确保算法有足够的迭代次数来处理所有的最短路径，而内层循环则是对具体的边进行操作，两者各自独立，共同配合完成算法的整个过程。

疑问 2

看起来 for each edge (u, v, w) in edges 中，u、v 是可以对换的，所以 distance[u] + w < distance[v] 为何不需要再判断 distance[v] + w < distance[u]

疑问 2 的回答

在 for each edge (u, v, w) in edges 这个循环中，u 和 v 代表边的起点和终点，它们并不是可以随意对换的。

• 有向图中
  • 边是有方向的，从 u 到 v 可能与从 v 到 u 的距离不同，因为可能存在一条从 u 到 v 的边，但不一定存在反方向的边，即便存在，其权重 w 也可能不同。
  • 算法中的 distance[u] + w < distance[v] 这个条件是在尝试进行松弛操作，意思是：如果你可以通过点 u 到达点 v，并且这样做得到的路径比你目前记录的到点 v 的路径更短，那么就更新到点 v 的最短路径距离。这是一个单向的检查。
• 无向图中
  • 通常在输入的边集 edges 中，每条无向边会被转换成两条有向边，即一条从 u 到 v，另一条从 v 到 u，它们的权重是相同的。这样，算法在遍历边的时候自然会检查每个方向的距离。
  • 因此，不需要额外再判断 distance[v] + w < distance[u]，因为算法会在遍历到边 (v, u, w') 时自然地处理这种情况，其中 w' 是从 v 到 u 的边的权重。在无向图中 w' 和 w 是相同的，在有向图中则可能不同。这保证了算法考虑了所有方向的边。