V: 0
Phase: -
BF pass: -
Source: -
Relaxations: 0
min w': -
Neg cycle: no
super-source q
Bellman-Ford relaxing
Dijkstra source
settled
tight edge (w'=0)
Big-O
| Phase | Cost | Note |
|---|---|---|
| Bellman-Ford (potentials) | O(V·E) | once, detects neg cycle |
| Reweight | O(E) | one sweep, w' ≥ 0 |
| V × Dijkstra (binary heap) | O(V·E·log V) | dominant term |
| Un-reweight | O(V²) | one subtraction per pair |
| Total | O(V·E·log V) | beats Floyd-Warshall O(V³) on sparse |