Graph Patterns: Shortest Path with Negative Weights (Bellman-Ford)
Dijkstra's algorithm is fast, but it completely breaks down if a graph contains negative edge weights. The Bellman-Ford algorithm handles negative weights and detects infinite negative cycles.
Introduction
If a graph has negative edge weights (representing financial gains, or specific time-travel logic in algorithmic puzzles), Dijkstra's greedy approach will fail because it assumes adding edges always increases the total path length.
The Bellman-Ford Strategy
The Bellman-Ford algorithm is purely brute-force edge relaxation.
In a graph with $V$ vertices, the longest possible path without cycles can have at most $V-1$ edges. Therefore, Bellman-Ford loops exactly $V-1$ times. In every single loop, it attempts to relax every single edge in the entire graph.
By the end of the $V-1$ passes, all shortest paths are mathematically guaranteed to have propagated.
Negative Cycle Detection
If a graph has a loop where the total sum of weights is negative, you could loop through it infinitely to achieve a path distance of negative infinity.
To detect this, Bellman-Ford runs one final $V^{th}$ pass. If any edge can still be relaxed and minimized on this final pass, it proves the graph contains an infinite negative weight cycle.
Implementation
class Solution {
public int[] bellmanFord(int V, ArrayList<ArrayList<Integer>> edges, int src) {
int[] dist = new int[V];
Arrays.fill(dist, (int)(1e8));
dist[src] = 0;
// Relax all edges V - 1 times
for (int i = 0; i < V - 1; i++) {
for (ArrayList<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
int wt = edge.get(2);
if (dist[u] != 1e8 && dist[u] + wt < dist[v]) {
dist[v] = dist[u] + wt;
}
}
}
// Nth relaxation to check for negative cycles
for (ArrayList<Integer> edge : edges) {
int u = edge.get(0);
int v = edge.get(1);
int wt = edge.get(2);
if (dist[u] != 1e8 && dist[u] + wt < dist[v]) {
// If distance still decreases, a negative cycle exists
return new int[] { -1 };
}
}
return dist;
}
}