Johnson 算法

Johnson 算法简介

Johnson 算法是一种图算法，用于查找加权有向图中所有顶点对之间的最短路径。该算法由 Donald B. Johnson 于 1977 年开发，特别适用于处理可能具有负边权重的图。这克服了 Dijkstra 或 Floyd-Warshall 等其他算法的局限性，这些算法在处理负边权重时可能无法正常工作，或对于大型图效率较低。以下是 Johnson 算法的简化概述：图转换：算法首先转换输入的原始图，以去除负边权重并使其适用于传统的单源最短路径算法。它通过添加一个新顶点并用零权重边将其连接到所有现有顶点来实现此目的。这有效地将原始图转换为所有边权重均为非负的图。

1. Bellman-Ford 算法：下一步是在转换后的图上使用 Bellman-Ford 算法，查找从新添加的顶点到所有其他顶点的最短路径。此步骤有助于识别和处理图中的负权重循环，并计算每个顶点的势值。
2. 边权重重新计算：使用 Bellman-Ford 步骤获得的势值，Johnson 算法重新计算转换后图的边权重。这些重新计算的权重经过调整，以确保它们都是非负的。此步骤确保图已准备好进行高效的最短路径计算。
3. Dijkstra 算法：使用转换后的图和调整后的边权重，算法对图中的每个顶点应用 Dijkstra 算法。这使得它能够找到从每个顶点到所有其他顶点的最短路径。由于边权重现在是非负的，Dijkstra 算法可以最优地工作。Johnson 算法的主要优点是它能够处理具有负边权重的图，同时保持效率。通过修改图并调整边权重，它为所有顶点对最短路径问题提供了一个解决方案，这在网络路由、交通规划和网络分析等各种应用中非常有用。但是，需要注意的是，Johnson 算法由于涉及额外的图转换和势值计算步骤，因此具有一定的计算开销。

Johnson 算法的优点

Johnson 算法为解决加权有向图的最短路径问题提供了多种优势，尤其与其他算法（如 Dijkstra 或 Floyd-Warshall 算法）相比。其主要优势包括：

1. 处理负边权重：Johnson 算法最突出的优点之一是它能够处理具有负边权重的图。虽然 Dijkstra 和 Floyd-Warshall 等算法可能给出错误结果或无法处理此类图，但 Johnson 算法可以在查找最短路径之前转换图，使其所有边权重均为非负。
2. 稀疏图上的效率：Johnson 算法在稀疏图上通常比 Floyd-Warshall 算法更有效。这种效率源于它仅处理构成最短路径一部分的边，从而在边相对较少的图中实现更快的性能。
3. 密集图上的较低时间复杂度：在具有大量顶点和边的密集图中，Johnson 算法在时间复杂度方面可能比 Floyd-Warshall 更高效。这是因为 Floyd-Warshall 的时间复杂度为 O(V^3)，而 Johnson 算法的时间复杂度受边数的影响，对于密集图可能更有利。
4. 负权环的隔离：Johnson 算法不仅能找到最短路径，还能检测图中的负权重循环。这有助于检测和报告此类循环的出现，这对于网络分析等各种应用非常有价值。
5. 处理不同图类型的多功能性：Johnson 算法具有多功能性，可以处理各种图，包括带有负边权重、密集或稀疏图，以及带或不带重构的负权重。这种多功能性使其成为交通规划、网络路由和社会网络分析等许多领域的宝贵工具。
6. 针对以下问题的优化：如果您想找到同一图上具有不同起始点的多个最短路径，Johnson 算法可能比多次运行 Dijkstra 算法更有效。它在 Bellman-Ford 步骤中计算所需信息，这些信息可以在后续查询中重复使用。尽管有其优点，但重要的是要注意，Johnson 算法会产生一些计算成本，主要是由于 Bellman-Ford 步骤和势值计算。

因此，它可能并非总是适用于所有图场景的最有效选择。算法的选择应取决于图的特定特性和所考虑问题的要求。

Johnson 算法的缺点

尽管 Johnson 算法具有多种优点，但它也有一些缺点和限制：计算开销：Johnson 算法包括 Bellman-Ford 算法和势值计算等额外步骤来处理负边权重。这些步骤增加了计算开销，使其效率低于一些其他非负权重图算法。

1. 实现难度：与 Dijkstra 或 Floyd-Warshall 等较简单的算法相比，Johnson 算法的实现可能更困难。图转换、势值计算和边权重调整需要仔细处理，并且可能容易出错。
2. 内存使用：Johnson 算法可能比其他算法消耗更多的内存，尤其是在大型图中。这是因为必须存储额外的​​数据结构来处理图的转换和每个顶点的势值。
3. 对密集图的效率：Johnson 算法对于稀疏图可能更有效，但对于密集图，其性能可能不如 Floyd-Warshall 算法。对于密集图，Johnson 算法的计算成本可能会抵消其优势。
4. 额外的空间复杂度：除了内存使用外，Johnson 算法还引入了额外的空间复杂度，因为必须存储转换后的图和势值。在内存受限的环境中工作时，这可能是一个问题。
5. 适用性有限：Johnson 算法主要用于查找加权有向图中所有顶点对之间的最短路径。对于其他类型的图问题或负边权重不是问题的情况，它可能不是最合适的选择。
6. 性能可变性：Johnson 算法的性能可能因输入图的特定特性而异，例如边权重的分布和负权重周期是否存在。在某些情况下，它的性能可能不如简单的算法。
7. 路径重建缺失：与 Dijkstra 算法不同，Johnson 算法不直接提供实际最短路径的信息。如果您需要重建路径及其长度，可能需要额外的计算，这会使实现复杂化。

总而言之，尽管 Johnson 算法是处理负边权重图的宝贵工具，并且具有多种优点，但它也存在一些缺点，尤其是在计算成本、内存使用和复杂性方面。算法的选择应基于任务的特殊性以及要分析的图。

Johnson 算法的历史

Johnson 算法是计算机科学领域，特别是在图论领域中广泛使用的算法。它用于查找加权有向图中所有顶点对之间的最短路径，即使图具有负边权重，只要没有负权重环路即可。该算法由 Donald B. Johnson 于 1977 年开发。Johnson 算法是 Dijkstra 算法和 Floyd-Warshall 算法的扩展，这两者都用于查找图中的最短路径。以下是 Johnson 算法的简史：

1. 早期最短路径算法：在 Johnson 算法开发之前，有各种用于查找图中最短路径的算法。Edsger W. Dijkstra 于 1956 年提出的 Dijkstra 算法，以及 Robert W. Floyd 于 1962 年和 Stephen Warshall 于 1962 年开发的 Floyd-Warshall 算法，是用于此目的的两个著名算法。然而，这些算法存在局限性，尤其是在处理包含负权重边或环路的图时。
2. Johnson 算法开发（1977 年）：Donald B. Johnson 于 1977 年提出了他的算法，以解决早期算法的局限性。Johnson 算法结合了 Dijkstra 算法和 Floyd-Warshall 算法的思想，用于查找图中的所有最短路径，包括具有负权重边的图，并避免了 Floyd-Warshall 算法在密集图中的低效。
3. 关键贡献：Johnson 算法的创新之处在于，它通过添加一个连接到所有其他顶点且权重为零的虚拟顶点来转换原始图。通过这种转换，算法可以处理负权重边并有效地查找最短路径。创建转换后的图后，使用 Dijkstra 算法查找从虚拟顶点到所有其他顶点的最短路径。然后调整这些数据以计算所有顶点对之间的最短路径。
4. 应用：Johnson 算法在交通、网络路由和数据处理等各种领域都有应用。它在图可能具有负权重边但没有负权重循环的情况下特别有用，这在许多现实世界的场景中是一个常见假设。
5. 复杂性和发展：Johnson 算法的时间复杂度通常为 O(V^2 log V + VE)，其中 V 是顶点数，E 是边的数量。研究人员还开发了 Johnson 算法的变体和改进，使其在实践中更有效。总之，Johnson 算法为图算法领域做出了重要贡献，因为它提供了在负边图上查找所有最短路径的能力，同时避免了其他算法的缺点。在理解网络和图中的最短路径至关重要的各种应用中，它一直是一个宝贵的工具。

Johnson 算法的应用

Johnson 算法是一种图论算法，用于查找加权有向图中所有顶点对之间的最短路径。只要没有负权重环路，它就可以处理正负边权重都存在的图。该算法在各种应用中特别有用，包括：

1. 网络路由：Johnson 算法可用于在互联网等计算机网络中查找最短路径，以优化数据路由并最大限度地减少延迟。
2. 交通和物流：它可以帮助优化交通和物流路线，例如查找送货卡车的短程路线或确定航空公司时刻表中最高效的航班连接。
3. 社交网络分析：在社交网络分析中，Johnson 算法可用于查找社交网络中个体之间的最短路径，这对于理解信息流、影响力或关系结构非常有用。
4. 城市规划：城市规划者可以使用此算法确定城市内的最佳交通路线，以帮助减少交通拥堵并提高公共交通效率。游戏开发：游戏开发者可以使用 Johnson 算法来实现游戏角色或对象的寻路算法。这对于创建逼真且响应迅速的游戏环境非常重要。
5. 电路设计：在电子电路设计中，Johnson 算法可用于查找复杂组件连接中的最短路径，从而减少信号传播延迟并优化电路效率。
6. 地理信息系统 (GIS)：GIS 通常涉及空间数据的分析，Johnson 算法可用于查找地图上位置之间的最短路线。这在 GPS 导航和地理空间分析等应用中很有价值。
7. 项目规划：在项目管理中，Johnson 算法可用于确定项目网络中任务之间的最短路径，这有助于识别关键路径并优化项目进度。
8. 优化问题：Johnson 算法可以改编以解决各种优化问题，例如旅行商问题，通过查找所有城市对之间的最短路径然后选择最佳路线。
9. 科学研究：它广泛用于科学研究，尤其是在生物学等领域，它可以帮助分析蛋白质-蛋白质相互作用网络或研究生态网络。
10. 经济和金融：在经济建模中，Johnson 算法可用于计算金融网络（如银行系统或股票交易所网络）中的最短路径。
11. 交通规划：交通规划者可以使用此算法来优化交通信号灯时间，设计高效的交通网络并减少交通拥堵。总而言之，Johnson 算法是一种多功能的工具，可用于解决各种需要查找加权有向图中最短路径的优化和寻路问题。

伪代码

上面的伪代码提供了 Johnson 算法的概述。您需要根据您选择的编程语言和数据结构来实现 AddVertex、AddEdge、BellmanFord、RemoveVertex 和 Dijkstra 等函数。请注意，BellmanFord 函数会检查负权重循环。如果检测到此类周期，算法将终止，因为 Johnson 算法无法处理具有负权重周期的图。如果没有检测到负权重周期，算法将遍历图并使用 Dijkstra 算法查找每个顶点的最短路径。

Johnson 算法的 C++ 程序

Johnson 算法用于查找加权有向图中所有顶点对之间的最短路径。当图可能包含负权重边时，尤其有用，只要没有负权重环路即可。以下是 C 程序提供的理论解释：

1. 结构 Edge：一个结构，用于表示具有源、目标和权重的边。
2. vector graph：一个 vector，用于存储图的边。vector distance：一个 vector，用于存储从源顶点到所有其他顶点的距离，由 Bellman-Ford 和 Dijkstra 算法使用。
3. AddEdge：AddEdge 函数用于将边添加到图中。它接受边的源、目标和权重，并将其添加到图的 vector 中。
4. Bellman-Ford 算法：BellmanFord 函数应用 Bellman-Ford 算法来查找从给定源顶点到所有其他顶点的最短距离。它将所有顶点的距离重置为 INT_MAX，除了原点，原点为 0。它重复松弛 V-1 次边，其中 V 是图中的顶点数。在每次迭代中，它会检查所有边，并在找到更短的路径时更新每个顶点的距离。在 V-1 次迭代之后，该函数会检查负权重周期。如果找到，则返回 false，表示 Johnson 算法无法继续。否则，它返回 true，并且从原点到所有其他顶点的距离存储在 distance vector 中。
5. Dijkstra 算法：Dijkstra 函数应用 Dijkstra 算法来查找从给定原点到所有其他顶点的最短距离。它使用优先队列（最小堆）来有效地选择距离最短的顶点。它以与 Bellman-Ford 算法相同的方式迭代松弛边并更新距离，但仅针对单个原点。
6. Johnson 算法：JohnsonAlgorithm 函数使用 Johnson 算法来查找图中所有顶点对的最短路径。首先，将一个新顶点添加到图中，并用零权重边将其连接到所有现有顶点。然后，它使用 Bellman-Ford 算法查找从新顶点到所有其他顶点的距离。如果检测到负权重循环，算法将无法继续。如果没有负权重循环，它会重新加权边，使所有边权重不再为负。最后，它对图中的每个顶点应用 Dijkstra 算法来查找所有顶点对的最短路径，并将结果存储在一个二维 vector 中。
7. main 函数：在 main 函数中，程序从用户那里获取关于图中顶点数和边数的信息，以及边的详细信息（源、目标和权重）。然后调用 JohnsonAlgorithm 函数来计算所有顶点对的最短路径。将打印结果，如果两个顶点之间没有路径，则打印“INF”表示无穷大。总之，此 C++ 程序将 Bellman-Ford 和 Dijkstra 算法与 Johnson 算法相结合，用于在加权有向图中查找所有顶点对之间的最短路径，同时处理负权重边并检测负权重周期。

示例输出

Enter the number of vertices and edges: 4 5
Enter the edges (source, destination, weight):
0 1 1
0 2 4
1 2 2
1 3 5
2 3 1

Johnson 算法的 Java 程序

1. Graph 类：应用程序定义了一个 Graph 类来表示有向图，其中包含添加边、执行 Bellman-Ford 和 Dijkstra 算法的方法。
2. Edge 类：在 Graph 类中，有一个名为 Edge 的内部类，用于表示图中的一条边。每条边都有一个源顶点、一个目标顶点和一个权重。
3. addEdge() 方法：addEdge 方法用于将边添加到图中。它接受三个参数：源顶点、目标顶点和边权重，并将边添加到边的列表中。
4. BellmanFord() 方法：此私有方法实现 Bellman-Ford 算法，以查找从给定源顶点到图中所有其他顶点的最短距离。它返回一个距离数组。初始化一个 dist 数组来存储从给定顶点到所有其他顶点的最短距离。将所有距离设置为 Integer.MAX_VALUE，除了源顶点，其值为 0。迭代 V-1 次，其中 V 是顶点数：对于边列表中的每条边，检查是否可以通过给定顶点找到到目标顶点的更短路径。如果是，则替换距离。
5. JohnsonAlgorithm() 方法：此方法实现 Johnson 算法，该算法查找所有顶点对之间的最短路径。初始化一个长度为 V 的 h 数组来存储每个顶点的势值。最初，所有势值都设置为 0。向图中添加一个新顶点 V，并用权重为 0 的边将其连接到所有其他顶点。此步骤对于处理具有负边权重的图至关重要。运行 Bellman-Ford 以查找从虚拟顶点 V 到所有其他顶点的最短距离。从图中删除虚拟顶点 V 及其边。更新图中的边权重以考虑势值 h。迭代所有顶点，并运行 Dijkstra 算法以查找从每个顶点到所有其他顶点的最短路径。Dijkstra() 方法为每个顶点调用一次。Dijkstra() 方法：此私有方法实现 Dijkstra 算法，以查找从给定源顶点到所有其他顶点的最短路径。初始化一个 dist 数组来存储从给定顶点到所有其他顶点的最短距离。将所有距离设置为 Integer.MAX_VALUE，除了源顶点，其值为 0。将源顶点添加到优先队列中，距离为 0。当优先队列不为空时，执行以下操作：
   1. 从优先队列中删除距离最小的顶点。
   2. 松弛与此顶点相关的边以更新距离。
   3. 打印从给定顶点到所有其他顶点的最短距离。
6. main() 方法：在 main 方法中，创建一个示例图，添加边，然后实现 Johnson 算法以查找所有顶点对之间的最短路径。

示例输出

Shortest distances from vertex 0:
Vertex 0: 0
Vertex 1: -1
Vertex 2: 2
Vertex 3: -2
Vertex 4: 1

Shortest distances from vertex 1:
Vertex 0: 3
Vertex 1: 0
Vertex 2: 3
Vertex 3: 1
Vertex 4: 2

Johnson 算法的 Python 程序

1. 图表示：程序定义了 Graph 类来描述图。它使用邻接列表来存储边，并存储图的顶点数。
2. Bellman-Ford 算法：Bellman-Ford 方法用于实现 Bellman-Ford 算法以进行边重构。它计算从给定源到所有其他顶点的最短距离，并检测负权重周期。该算法执行 V-1 次迭代，其中 V 是顶点数，松弛边，并在找到更短的路径时更新距离（dist）。
3. Dijkstra 算法：Dijkstra 方法应用 Dijkstra 算法来查找从给定源到图中所有其他顶点的最短距离。它使用优先队列（最小队列）来有效地选择具有最小初始距离的顶点。该算法迭代地选择具有最小初始距离的顶点，在找到更短的路径时更新邻居的距离，并一直持续到所有顶点都被处理。
4. Johnson 算法：JohnsonAlgorithm 方法实现了 Johnson 算法，该算法结合了 Bellman-Ford 和 Dijkstra 算法：它向图中添加了虚拟顶点，并将其连接到所有其他顶点，其边权重为 0。然后，它使用 Bellman-Ford 算法对边进行重构并检查负权重周期。如果存在负权重循环，它会报告错误并退出。如果没有负循环，它会删除虚拟顶点，并使用 Dijkstra 算法重新计算所有顶点对的最短路径。
5. 在程序的 main 部分：通过添加指定权重的边来创建一个示例图。Johnson 算法用于查找所有顶点对之间的最短路径。将打印出结果的最短路径。总的来说，Johnson 算法提供了一种有效的方法来查找图中的所有最短路径，优雅地处理负权重边，并在存在时检测负权重周期。这首先通过重构图使所有边权重非负，然后应用 Dijkstra 算法查找最短路径来实现。

示例输出

The shortest path from 0 to 0 is 0
The shortest path from 0 to 1 is -5
The shortest path from 0 to 2 is -1
The shortest path from 0 to 3 is -4

Johnson 算法的结论

Johnson 算法是一种解决加权有向图中所有顶点对最短路径问题的有效方法，即使图包含负边权重。以下是总结 Johnson 算法主要点的结论：

• 处理负边权重：Johnson 算法可以处理具有负边权重的图，包括带有负权周期的图。这是通过重构图的边，使其所有边权重非负，从而可以使用 Dijkstra 或 Bellman-Ford 等传统的最短路径算法来实现的。算法步骤：

步骤 1：添加一个新顶点，并用零权重边将其连接到所有现有顶点。

步骤 2：在新增顶点上运行 Bellman-Ford 算法，计算从它到所有其他顶点的最小距离。如果在该步骤中检测到负循环，算法将终止，因为它无法处理包含负权循环的图。

步骤 3：根据步骤 2 中计算的距离，重新加权原始图的边。

步骤 4：要计算最短路径，请从图中的每个顶点运行 Dijkstra 算法或任何其他期望的单源最短路径算法。

• 时间复杂度：Johnson 算法的时间复杂度为 O(V^2 log(V) + VE)，其中 V 是图中的顶点数，E 是边数。Bellman-Ford 步骤控制了时间复杂度，这使得它在密集图上的效率不如 Floyd-Warshall 等其他算法。
• 用例：Johnson 算法在处理同时具有正负边权重的图时特别有用，或者当您想要查找图中所有顶点对之间的最短路径时。它不能处理带有负权环路的图。如果发生负权环路，它会在 Bellman-Ford 阶段被检测到，算法将无结果地结束。总之，Johnson 算法是一种通用的方法，用于在没有负权环路的情况下查找负边权重的图中的所有顶点对最短路径。它能够转换图的边权重，然后应用标准的 shortest-path 算法，使其成为图论和网络分析中的宝贵工具。但是，其时间复杂度可能会限制其在非常大或密集图上的实用性。