Ý nghĩa thực tế của thuật toán Johnson

Johnson算法是一种用于解决边数与节点数关系为O(n^2)的带宽图最短路径问题的算法。它是一种结合了 Dijkstra 算法和 Bellman-Ford 算法的技术，使用负权重环检测器消除负权重的影响。该算法的时间复杂度为O(n^2+m log n)。



Johnson算法是一种用于解决多源中最短路径问题的算法。它通过将图中的边转换为虚拟起点的边来解决该问题。



约翰逊算法的一个明显缺点是，在将边取为负后，它不能用于具有负边的图。这是因为负边沿导致最长路径不存在。另外，Johnson 算法的时间复杂度为 O(n^2 * log(n)+m * log(n))，其中 n 是顶点数，m 是边数。与其他多源最短路径算法相比，Johnson 算法具有更高的时间复杂度。另外，Johnson 算法需要 Bellman-Ford 或 Dijkstra 图来评估负循环，并且使用 Dijkstra 算法多次优化堆，因此空间复杂度也较大。



例如，假设有一个具有 5 个节点（A、B、C、D、E）和 7 个边（AB、BC、CD、DE、AD、BE、CD、BE、CE）的图。现在，如果您需要从 A、B、C 三个点到端点 E 的最短路径，则可以使用 Johnson 算法。



首先，将虚拟起点S添加到图中，并将S到A、B、C的边设置为0。然后使用Bellman-Ford算法找到从S到其他点的最短路径。然后将图中从 S 到该边的两个端点的最短路径长度的所有边权限相加。最后利用Dijkstra算法求出从A、B、C到E的最短路径。



在本例中，Johnson 算法将得到从 A 到 E、B 到 E、C 到 E 的最短路径为 [A, D, E], [B, E]。

本文转载自：https://www.teamdoc.cn/archives/2937