Graphs.jl
Graphs.jl copied to clipboard
Time complexity of Johnson's algorithm wrongly stated in documentation
Description of bug Describe the bug clearly and concisely.
The documentation to Johnson's all-pairs shortest path algorithm is stated as O(|V||E|). This cannot be true, in particular if Dijkstra's algorithm is finally called for weighted graphs. If Dijkstra's algorithm uses a Fibonacci heap (I didn't look if this is the case here), the runtime is O(|V|^2 log |V|+|V|⋅|E|), which is a big difference for sparse graphs. Only in case of an unweighted graph, one can achieve time O(|V||E|) by calling breadth first search from each node.