Johnson算法是一种用于解决带权图的最短路径问题的算法，特别适用于边数与节点数之间关系为O(n^2)的情况。它结合了Dijkstra算法和Bellman-Ford算法，通过使用一个负权重的环检测器来消除负权重的影响。Johnson算法的时间复杂度为O(n^2+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]。

此算法可以在O(V^2lgV+VE)的时间内找到所有结点对之间的最短路径。对于稀疏图而言，Johnson算法表现要优于Floyd算法。且Johnson算法要么返回一个包含所有结点对的最短路径权重的矩阵，要么报告图中含有负权环。