最短路径：贝尔曼-福特 vs. 约翰逊
我很难理解约翰逊算法的用处。我认为对于具有该领域知识的人来说，这个问题听起来一定很愚蠢，但我无法弄清楚。根据维基百科，约翰逊算法使用贝尔曼福特算法将边的权重转换为非负权重，然后使用迪杰斯特拉算法找到最短路径。但贝尔曼福特算法也是一种寻找最短路径的算法。为什么我们不直接使用从贝尔曼福特算法获得的最短路径呢？
I have difficulties in understanding the usefulness of the Johnson Algorithm. I think the question must sound really stupid for someone with knowledge in this area, but I cannot figure it out. According to Wikipedia, the Johnson Algorithm uses the Bellman Ford Algorithm to transform the weights of the edges to non-negative weights and then uses the Dijkstra Algorithm to find the shortest path. But the Bellman Ford Algorithm is also an algorithm to find the shortest path. Why don't we just use the shortest path that we get from the Bellman Ford Algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Bellman-Ford 算法找到从单个源到所有图顶点的最短路径（“单源最短路径”）。 Johnson 的算法找到从每个顶点到每个其他顶点的最短路径（“所有对最短路径”），因此它相当于从图中的每个可能的起始顶点运行 Bellman-Ford。
The Bellman-Ford algorithm finds the shortest path from a single source to all graph vertices ("single-source shortest paths"). Johnson's algorithm finds the shortest path from every vertex to every other vertex ("all-pairs shortest paths"), and so it is equivalent to running Bellman-Ford from every possible start vertex in your graph.
我知道我参加这个聚会迟到了，但我只是偶然发现了这个问题，因为我只是在问自己同样的事情。
为了更好地理解，我想指出约翰逊算法的第一步实际上是创建一个新图。它通过巧妙地使用 Bellman-Ford 算法将原始图（可以具有负边）转换为不具有负边的不同（但等效）图来实现此目的。这个新图现在可以安全地与 Dijkstra 算法一起使用。然后使用 Dijkstra 算法有效地计算其他两个答案提到的“所有对最短路径”。
可以在这里找到一个很好的解释：http://www.geeksforgeeks.org/johnsons-algorithm/
I know I am late to this party, but I just stumbled upon the question because I was just asking myself the same thing.
For better understanding I would like to point out that the first step of Johnson's Algorithm actually creates a new graph. It does this by cleverly using the Bellman-Ford algorithm to transform the original graph (which can have negative edges) into a different (but equivalent) graph that does not have negative edges. This new graph is now safe to be used with Dijkstra's Algorithm. Dijkstra's Algorithm is then used to efficiently calculate the "all-pairs shortest paths" that the two other answers mention.
A nice explanation can be found here: http://www.geeksforgeeks.org/johnsons-algorithm/
Bellman Ford 算法用于查找从单个顶点（源）到所有其他顶点的最短路径，而 Johnson 算法用于查找所有对最短路径。如果您想在 C 中实现 Johnson 算法，请告诉我。
The Bellman Ford algorithm is used for finding the shortest path from single vertex(source) to all other vertices whereas Johnson algorithm is used to find all pair shortest path.If you want implementation of Johnson algorithm in C,inform me.