Bellman-Ford
Single-source shortest paths that tolerates negative edge weights. It relaxes every edge V−1 times; a further improving relaxation reveals a negative-weight cycle.
- Category
- Graphs
- Time complexity
- O(V·E)
- Space complexity
- O(V)
Pseudocode
dist[src] ← 0 repeat V−1 times: relax every edge extra relaxation ⇒ negative cycle
Reference implementation
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w