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]。