Johnson’s Algorithm

When tasked with finding the shortest paths between all pairs of vertices, calculating the shortest paths between them seems easy enough. In the presence of negative edge weights, our first instinct is to call the Bellman-Ford algorithm from each vertex.

This would certainly guarantee the detection of negative-weight cycles in the digraph. On the other hand, it would take a whopping $O(n^4)$ time in the worst case.worstcasejohnson