Johnson算法求稀疏图中所有顶点对最短路径 题目描述 给定一个可能包含负权边但不含负权环的稀疏有向图，要求找到图中所有顶点对之间的最短路径距离。稀疏图是指边的数量|E|远小于顶点数量|V|的平方（即|E| < < |V|²）的图。Johnson算法能高效解决这个问题，特别适合稀疏图。 解题过程 1. 问题分析 我们需要计算所有顶点对(i,j)之间的最短路径距离 图可能包含负权边，但没有负权环（否则最短路径无意义） 稀疏图的特性使得我们需要选择适合的算法： Floyd-Warshall算法：O(|V|³)，适合稠密图 对每个顶点运行Dijkstra：O(|V|·|E|log|V|)，但Dijkstra不能处理负权边 Johnson算法通过对图进行重赋权，使得所有边权非负，然后对每个顶点运行Dijkstra 2. 算法核心思想 Johnson算法的关键洞察是：如果能找到一种方式重新分配边的权重，使得： 所有边权变为非负 任意两顶点间的最短路径保持不变 那么就可以对每个顶点使用高效的Dijkstra算法 3. 具体实现步骤 步骤1：添加虚拟顶点 在图中添加一个新的顶点s，该顶点不属于原图 从s向原图中的每个顶点添加一条权重为0的有向边 这样得到的新图记为G' 步骤2：计算虚拟顶点的单源最短路径 在G'上，以s为源点，运行Bellman-Ford算法 Bellman-Ford算法可以处理负权边，并能检测负权环 如果检测到负权环，算法终止（原问题无解） 否则，得到从s到每个顶点v的最短路径距离h(v) 步骤3：重赋权重 对于原图中的每条边(u,v)，其原始权重为w(u,v) 计算新的权重：ŵ(u,v) = w(u,v) + h(u) - h(v) 这个重赋权操作的关键性质： 所有新权重ŵ(u,v) ≥ 0（由三角不等式保证） 任意路径p = v₀→v₁→...→vₖ的长度变化为：原长度 + h(v₀) - h(vₖ) 步骤4：运行Dijkstra算法 在重赋权后的图上，对每个顶点u： 以u为源点运行Dijkstra算法，得到从u到所有其他顶点的距离δ'(u,v) 由于新图没有负权边，Dijkstra算法能正确工作 步骤5：还原实际距离 对于每对顶点(u,v)，实际最短距离为： δ(u,v) = δ'(u,v) - h(u) + h(v) 这个还原操作抵消了重赋权时引入的偏移量 4. 算法正确性证明 非负权重的证明： 对于任意边(u,v)，根据三角不等式： h(v) ≤ h(u) + w(u,v) 因此：ŵ(u,v) = w(u,v) + h(u) - h(v) ≥ 0 路径长度保持性证明： 对于路径p = v₀→v₁→...→vₖ： 新长度 = ∑ŵ(vᵢ₋₁,vᵢ) = ∑[ w(vᵢ₋₁,vᵢ) + h(vᵢ₋₁) - h(vᵢ) ] = 原长度 + h(v₀) - h(vₖ) 由于h(v₀)和h(vₖ)是常数，路径的相对顺序保持不变。 5. 时间复杂度分析 添加虚拟顶点和边：O(|V|) Bellman-Ford算法：O(|V|·|E|) 重赋权重：O(|E|) |V|次Dijkstra（使用二叉堆）：O(|V|·|E|log|V|) 总时间复杂度：O(|V|·|E|log|V|) 对于稀疏图（|E| = O(|V|)），这比Floyd-Warshall的O(|V|³)更优。 6. 算法优势 适合稀疏图，时间复杂度优于Floyd-Warshall 能处理负权边（只要没有负权环） 结合了Bellman-Ford和Dijkstra的优点 在实际应用中表现良好，特别是当图很大但相对稀疏时 Johnson算法通过巧妙的图变换，将含负权边的最短路径问题转化为标准的非负权最短路径问题，展现了图算法设计中"问题归约"的优美思想。