Johnson 全源最短路径算法学习笔记

如果你希望得到带互动的极简文字体验，请点这里

我们来学习johnson

Johnson 算法是一种在边加权有向图中找到所有顶点对之间最短路径的方法。它允许一些边权重为负数，但可能不存在负权重循环。它的工作原理是使用Bellman-Ford 算法来计算输入图的转换，该转换去除了所有负权重，从而允许在转换后的图上使用Dijkstra 算法。Johnson 算法是一种在边加权有向图中找到所有顶点对之间最短路径的方法。它允许一些边权重为负数，但可能不存在负权重循环。它的工作原理是使用Bellman-Ford 算法来计算输入图的转换，该转换去除了所有负权重，从而允许在转换后的图上使用Dijkstra 算法。
--维基百科

• 可以发现排序算法中最能够全源的只有Johnson 和 Floyd

最优情况:
全源最短路跑\(n\) 次 Bellman-Ford 算法解决，时间复杂度是\(O(n^2m)\),原始是Floyd的\(O(n^3)\)

我们可以更优，使用迪杰斯特拉\(O(nm \space logm)\)

但是我们还关注能否处理负边

所以只有SPFA,Floyd,贝尔曼,Johnson可以解决

原理解释

所以我们解决带负边的全源最短路时同时兼顾时间应该怎么做？

• 使用Dijkstra
  但是Dijkstra不能处理有负边的问题，所以我们可以使边变为正数,我们基本得到3个猜想:

1. 对每条边进行相同的增量，使所有边非负。
2. 改变图的结构，不改变图的性质，使Dijkstra可做。
3. 对每条边单独设计增量，使图的性质保证并且全图非负。

可以看出只有第三种是正确的。

为什么第一种不正确？

如上图(箭头错，1->3应该是3->1)3->2的最短路原本是-2(走上面)，但是对于边权+5的图(绿)就成了9(走下面)，路径发生了改变，不可取。

Johnson算法核心

建一个超级源，到所有点连0 权边，对超级源跑一遍SPFA，求出每个点的dis 值。重构原图边权，对于边