我很难理解 Johnson Algorithm 的用处.我认为这个问题对于有这方面知识的人来说一定听起来很愚蠢，但我想不通。根据维基百科，约翰逊算法使用贝尔曼福特算法将边的权重转换为非负权重，然后使用 Dijkstra 算法找到最短路径。但是贝尔曼福特算法也是一种寻找最短路径的算法。为什么我们不直接使用从 Bellman Ford 算法获得的最短路径？
最佳答案
Bellman-Ford 算法寻找从单个源到所有图形顶点的最短路径(“单源最短路径”)。约翰逊算法找到从每个顶点到每个其他顶点的最短路径(“所有对最短路径”)，因此它等效于从图中每个可能的起始顶点运行 Bellman-Ford。
关于algorithm - 最短路径 : Bellman-Ford vs. 约翰逊，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5316609/