johnsons_algorithm (937B)
1 # Johnson's algorithm 2 3 https://en.wikipedia.org/wiki/Johnson%27s_algorithm 4 5 - Uses [bellman_ford] for [single_source_shortest_path] on [super_source], gives 6 function h indicating the length of shortest path from super source to 7 each vertex 8 - abort if [negative_cycle] 9 - Then reweigh the edges: edge (u, v) is given weight w(u, v) + h(u) - h(v) 10 - Note: this is >=0, indeed if it were <0 then we get h(u) + w(u, v) < h(v) 11 contradicting [triangle_inequality] or witnessing a [negative_cycle] 12 - Then do [dijkstras_algorithm] with the new weights from every vertex 13 - Any path from s to t in the reweighted graph has weight that of the original 14 graph plus h(s)-h(t) ([telescoping_sum]) 15 - So the shortest paths returned are correct, up to adjusting them with the 16 value h(s)-h(t) 17 18 Time complexity O(n^2 log n + nm), so can be better than [floyd_warshall] for 19 [graph_sparse] 20 21 Up: [algorithm] for [all_pairs_shortest_path]