Graphs.jl icon indicating copy to clipboard operation
Graphs.jl copied to clipboard

Time complexity of Johnson's algorithm wrongly stated in documentation

Open graidl opened this issue 4 months ago • 1 comments

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.

graidl avatar Sep 26 '24 10:09 graidl