How does Bellman-Ford detect negative cycles in a weighted graph?
ā Interview Prompt: Explain Bellman-Ford O(VE) shortest path, why it handles negative weights, negative cycle detection, and comparison to Dijkstra.
Bellman-Ford relaxes all edges $V - 1$ times. Since the shortest path in a graph with $V$ vertices has at most $V - 1$ edges, $V - 1$ relaxation rounds are sufficient.
Negative Cycle Detection:
Perform one additional (Vth) relaxation pass. If any distance still decreases ā a negative cycle exists (paths can spiral to $-\infty$).
vs Dijkstra:
| | Dijkstra | Bellman-Ford |
|---|---|---|
| Negative weights | ā | ā |
| Time | $O((V+E)\log V)$ | $O(V \times E)$ |
| Negative cycle detect | ā | ā |
Code Implementation Example
function bellmanFord(V: number, edges: [number, number, number][], src: number): number[] | null {
const dist = new Array(V).fill(Infinity);
dist[src] = 0;
for (let i = 0; i < V - 1; i++) { // V-1 relaxation rounds
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// Vth pass: detect negative cycle
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
return null; // negative cycle detected!
}
}
return dist;
}Bellman-Ford handles negative weights and detects negative cycles. Use it when Dijkstra's non-negative weight constraint cannot be guaranteed.