Johnson算法求稀疏图中所有顶点对最短路径 题目描述 给定一个可能包含负权边但不含负权环的稀疏有向图，要求找出图中所有顶点对之间的最短路径距离。稀疏图是指边数|E|远小于顶点数|V|的平方（|E| < < |V|²）的图。Johnson算法能高效解决这个问题，特别适合稀疏图场景。 算法思路 Johnson算法的核心思想是通过重新赋权（reweighting）技术，消除图中的负权边，然后对每个顶点运行一次Dijkstra算法。它包含三个关键步骤： 添加虚拟顶点并计算势能函数 基于势能函数对边重新赋权 对每个顶点运行Dijkstra算法 详细解题过程 步骤1：添加虚拟顶点和计算势能函数 在原始图G中添加一个虚拟顶点s，并添加从s到原图中所有顶点的边，这些边的权重设为0 使用Bellman-Ford算法计算从s到所有顶点的最短距离h[ v]（这个h[ v ]就是势能函数） 如果检测到负权环，算法终止（因为存在负权环时最短路径无意义） 如果没有负权环，势能函数h[ v]满足三角不等式：h[ v] ≤ h[ u ] + w(u,v) 步骤2：边重新赋权 对于原图中的每条边(u,v)，计算新的权重：ŵ(u,v) = w(u,v) + h[ u] - h[ v ] 这个重新赋权操作的关键性质： 新权重ŵ(u,v)都是非负的（因为h[ v] ≤ h[ u ] + w(u,v)） 重新赋权保持最短路径结构（任意路径的长度变化只与起点终点有关） 步骤3：运行Dijkstra算法 移除虚拟顶点s，恢复原始图结构 对图中的每个顶点u： 以u为起点，在重新赋权后的图上运行Dijkstra算法 得到从u到所有顶点v的距离δ(u,v) 将距离还原：d(u,v) = δ(u,v) - h[ u] + h[ v ] 算法复杂度分析 添加虚拟顶点和运行Bellman-Ford：O(|V|·|E|) |V|次Dijkstra算法： 使用二叉堆：O(|V|·|E|log|V|) 使用斐波那契堆：O(|V|²log|V| + |V|·|E|) 总复杂度：O(|V|·|E| + |V|²log|V|)（使用斐波那契堆） 对于稀疏图（|E| = O(|V|)），复杂度为O(|V|²log|V|)，优于Floyd-Warshall的O(|V|³) 关键洞察 Johnson算法的巧妙之处在于通过势能函数将负权图转化为非负权图，从而能够使用更高效的Dijkstra算法。势能函数h[ v ]实际上为每个顶点提供了一个"高度"，重新赋权相当于让所有边都"下坡"走，从而消除负权边。