Tho*_*mas 3 algorithm shortest-path
我很难理解约翰逊算法的有用性.我认为这个问题听起来对于在这方面有所了解的人来说真的很愚蠢,但我无法弄明白.根据维基百科,约翰逊算法使用Bellman Ford算法将边缘权重转换为非负权重,然后使用Dijkstra算法找到最短路径.但Bellman Ford算法也是一种找到最短路径的算法.为什么我们不使用从Bellman Ford算法得到的最短路径？
Bellman-Ford算法找到从单个源到所有图顶点的最短路径("单源最短路径").Johnson的算法找到从每个顶点到每个其他顶点的最短路径("所有对最短路径"),因此它相当于从图中的每个可能的起始顶点运行Bellman-Ford.