我很难理解Johnson 算法的用处。我认为对于在这方面有知识的人来说，这个问题听起来一定很愚蠢，但我无法弄清楚。根据维基百科，约翰逊算法使用贝尔曼福特算法将边缘的权重转换为非负权重，然后使用 Dijkstra 算法找到最短路径。但贝尔曼福特算法也是一种寻找最短路径的算法。为什么我们不直接使用从贝尔曼福特算法中得到的最短路径？
问问题
2397 次
3 回答
8
Bellman-Ford 算法找到从单个源到所有图顶点的最短路径（“单源最短路径”）。约翰逊的算法找到从每个顶点到每个其他顶点的最短路径（“所有对最短路径”），因此它相当于从图中每个可能的起始顶点运行 Bellman-Ford。
于 2011-03-15T19:11:05.630 回答
1
我知道我参加这个聚会迟到了，但我只是偶然发现了这个问题，因为我只是在问自己同样的问题。
为了更好地理解，我想指出约翰逊算法的第一步实际上创建了一个新图。它通过巧妙地使用 Bellman-Ford 算法将原始图（可以具有负边）转换为不具有负边的不同（但等效）图来做到这一点。这个新图现在可以安全地与 Dijkstra 算法一起使用。然后使用 Dijkstra 算法有效地计算其他两个答案提到的“所有对最短路径”。
可以在这里找到一个很好的解释：http ://www.geeksforgeeks.org/johnsons-algorithm/
于 2015-01-12T16:28:34.953 回答
0
Bellman Ford 算法用于查找从单个顶点（源）到所有其他顶点的最短路径，而 Johnson 算法用于查找所有对最短路径。如果您想在 C 中实现 Johnson 算法，请通知我。
于 2014-11-03T02:49:21.003 回答