johnson算法的现实意义

Johnson算法是一种用于解决边数与节点数之间关系为O(n^2)的带权图的最短路径问题的算法。它是一种结合了Dijkstra算法和Bellman-Ford算法的技术，通过使用一个负权重的环检测器来消除负权重的影响。这种算法的时间复杂度为O(n^2+m log n)。

 

Johnson算法是一种用于解决多源最短路径问题的算法。它通过将图中的边权转换为虚拟起点的边权来解决问题。

 

Johnson算法的一个明显缺点是，在边权取负值之后，有负权边的图上不能使用该算法。这是因为负权边会导致最长路径不存在。另外，Johnson算法的时间复杂度为O(n^2 * log(n) + m * log(n))，其中n为顶点数，m为边数。相比于其他多源最短路径算法，Johnson算法的时间复杂度较高。还有一点就是Johnson算法需要先对图做一个Bellman-Ford或者Dijkstra来判断负环，并且需要多次使用堆优化的Dijkstra算法，所以空间复杂度也比较大。

 

例如，假设有一个图，其中包含5个节点（A、B、C、D、E）和7条边（A-B、B-C、C-D、D-E、A-D、B-E、C-E）。现在，如果要求从A、B、C三个起点到E终点的最短路径，可以使用Johnson算法。

 

首先，将虚拟起点S加入图中，并将S到A、B、C的边权设为0。然后，使用Bellman-Ford算法求S到其他各点的最短路径。接着，将图中所有边权加上S到该边的两个端点的最短路径长度。最后，使用Dijkstra算法求A、B、C到E的最短路径。

 

在这个例子中，Johnson算法将会得到A到E、B到E、C到E的最短路径分别为 [A,D,E], [B,E]。