Check out my first novel, midnight's simulacra!

Johnson's Algorithm

From dankwiki

An algorithm to find all vertex pair's shortest paths in a sparse directed graph. Edge weights but not cycles may be negative. The algorithm combines Bellman-Ford with Dijkstra.