You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
gdalle
changed the title
[BUG] Time complexity of Johnson's algorithm wrongly stated in documentation
Time complexity of Johnson's algorithm wrongly stated in documentation
Sep 28, 2024
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.
The text was updated successfully, but these errors were encountered: