我对Johnson算法的有用性感到困惑。我认为这个问题对于这个领域有知识的人来说可能听起来很愚蠢，但我无法理解它。根据维基百科，Johnson算法使用Bellman-Ford算法将边的权重转换为非负权重，然后使用Dijkstra算法找到最短路径。但是Bellman-Ford算法也是一种寻找最短路径的算法。为什么我们不能直接使用从Bellman-Ford算法得到的最短路径呢？
3个回答
8
Bellman-Ford算法可以找到从单个源点到所有图顶点的最短路径（“单源最短路径”）。Johnson算法可以找到每个顶点到其他每个顶点的最短路径（“全源最短路径”），因此等价于在图中从每个可能的起始顶点运行Bellman-Ford算法。
- Jeremiah Willcock
1
我知道我来晚了，但我刚好遇到了这个问题，因为我自己也在问同样的问题。
为了更好地理解，我想指出Johnson算法的第一步实际上创建了一个新图。它通过巧妙地使用Bellman-Ford算法将原始图（可能具有负边缘）转换为不具有负边缘的不同（但等效）图。现在可以安全地使用Dijkstra算法与这个新图一起使用。然后使用Dijkstra算法高效地计算出两个其他答案提到的“所有对最短路径”。
这里可以找到一个很好的解释：http://www.geeksforgeeks.org/johnsons-algorithm/
为了更好地理解，我想指出Johnson算法的第一步实际上创建了一个新图。它通过巧妙地使用Bellman-Ford算法将原始图（可能具有负边缘）转换为不具有负边缘的不同（但等效）图。现在可以安全地使用Dijkstra算法与这个新图一起使用。然后使用Dijkstra算法高效地计算出两个其他答案提到的“所有对最短路径”。
这里可以找到一个很好的解释：http://www.geeksforgeeks.org/johnsons-algorithm/
- hannes.koller
0
贝尔曼-福德算法用于查找单个顶点（源）到所有其他顶点的最短路径，而约翰逊算法用于查找所有对最短路径。如果您需要C语言中约翰逊算法的实现，请告诉我。
- user3590463
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接