Algorithms - Bellman-Ford and Floyd-Warshall - shortest paths with negative weights and all-pairs
Intro
At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:
- Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
- Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
- Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
- Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
- Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
- Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
- Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
- Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).
Bonus:
- Efficient prefix and pattern matching - solved by Trie and KMP String Search
- Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
- Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall
This post will be about shortest path problems when the weights may be negative: Bellman-Ford and Floyd-Warshall.
When to use
Dijkstra (see the Heaps post) is fantastic when all weights are non-negative, but as soon as negative edge weights appear (currency arbitrage, flight prices with refunds, or certain graph modeling tricks) Dijkstra fails.
Bellman-Ford solves the single-source shortest path problem with negatives and can detect negative cycles.
- single source, possible negative edges, need to detect negative cycles (O(V·E) is acceptable).
Floyd-Warshall solves the all-pairs shortest path problem in one shot and also detects negative cycles.
- dense graph (E ≈ V2), need distances between every pair of nodes, V ≤ 400 (O(V3) is fine).
Typical problems: cheapest flights with refunds, arbitrage detection, transitive closure, "find the city with the smallest number of reachable neighbors within a distance threshold".
Theory
Relaxing an edge means that if the path from source to a destination node is shorter if doing it via an intermediate node, we update the estimate for the distance from source to destination. The term comes from the fact that the distance to a node is an upper bound (a "relaxed" estimate) on the true shortest-path distance. When we find a better path, we relax (lower) that upper bound. The operation never increases the estimate, and after enough relaxations the estimates become exact shortest-path distances.
Bellman–Ford, Dijkstra, A*, Johnson's algorithm and others use edge relaxing.
Bellman-Ford
The core idea of the algorithm is to relax every edge |V|−1 times. After that, any further relaxation means a negative cycle exists.
Implementation:
int[] ShortestPath(int n, int[][] edges, int src)
{
const int halfMax = int.MaxValue / 2;
int[] dist = new int[n];
Array.Fill(dist, halfMax);
dist[src] = 0;
// Relax |V|-1 times
for (int i = 0; i < n - 1; i++)
{
foreach (var e in edges)
{
int u = e[0], v = e[1], w = e[2];
if (dist[u] != halfMax && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
// Check for negative cycle
foreach (var e in edges)
{
int u = e[0], v = e[1], w = e[2];
if (dist[u] != halfMax && dist[u] + w < dist[v])
return null; // negative cycle reachable from src
}
return dist;
}
int[][] edges = [
[0, 1, 5],
[1, 2, -3],
[0, 2, 10]
];
var dist = ShortestPath(3, edges, 0);
Console.WriteLine(dist != null
? string.Join(", ", dist) // 0, 5, 2
: "Negative cycle detected");Complexity
- Time: O(V*E)
- Space: O(V)
The O(V*E) time bound follows directly from |V| passes over the edge list, and the space is O(|V|). In practice the algorithm often converges early (no updates in a pass), but the worst-case analysis guarantees correctness even on adversarial inputs with negatives. This combination of dynamic-programming clarity, negative-weight tolerance, and built-in cycle detection makes Bellman-Ford the theoretical foundation for many more advanced shortest-path algorithms (Johnson’s algorithm, difference constraints, etc.).
The Bellman-Ford algorithm solves the single-source shortest-paths problem on a directed graph by exploiting the optimal substructure of shortest paths via dynamic programming. After the k-th iteration, every distance value in the array is already the shortest possible path from the source that uses at most k edges.
Each full pass over every edge checks whether there is a better way to reach any node by coming through one additional edge. Because the previous pass already had the best answers using up to k-1 edges, this new pass simply improves the answer to the best version that now allows one more edge.
A simple path in a graph can never use more than n-1 edges; if it did, it would have to visit the same node twice and therefore contain a cycle. That means after exactly n-1 complete passes, the array already holds the true shortest paths from the source to every reachable node, provided there are no negative cycles.
One final extra pass is then performed. If any distance can still be made smaller, it means there must be a negative cycle reachable from the source, because otherwise the distances would already be optimal and no further improvement would be possible. This extra check is what gives Bellman-Ford its ability to detect negative cycles, something Dijkstra cannot do.
Floyd-Warshall - shortest path
Floyd-Warshall starts with a table that only knows the direct edges between every pair of nodes (infinity for no connection). Then it goes through every possible intermediate node, one by one, and for every possible pair of start and end nodes it updates the table if the path through there becomes shorter.
Here is the implementation:
int[][] AllPairsShortestPath(int n, int[][] edges)
{
const int halfMax = int.MaxValue / 2;
var dist = new int[n][];
for (var i = 0; i < n; i++)
{
dist[i] = new int[n];
Array.Fill(dist[i], halfMax);
dist[i][i] = 0;
}
foreach (var e in edges)
{
int u = e[0], v = e[1], w = e[2];
dist[u][v] = Math.Min(dist[u][v], w);
}
for (var k = 0; k < n; k++)
for (var i = 0; i < n; i++)
for (var j = 0; j < n; j++)
if (dist[i][k] != halfMax && dist[k][j] != halfMax)
dist[i][j] = Math.Min(dist[i][j], dist[i][k] + dist[k][j]);
// Negative cycle check
for (var i = 0; i < n; i++)
if (dist[i][i] < 0)
return null;
return dist;
}
int[][] edges = [
[0, 1, 5],
[1, 2, -3],
[0, 2, 10]
];
var distMatrix = AllPairsShortestPath(3, edges);
Console.WriteLine("0 -> 2: " + distMatrix[0][2]); // 2Complexity
- Time: O(V3)
- Space: O(V2)
The Floyd-Warshall algorithm solves the all-pairs shortest-paths problem on a directed graph by using dynamic programming to consider every possible intermediate node in a systematic way. It begins with a distance table that contains only the direct edge weights between every pair of nodes. Then, for each potential stopping point in the graph, it checks every possible pair of start and end nodes and updates the recorded distance if routing through that stopping point produces a shorter total path.
Because it exhaustively tries every possible intermediate node exactly once, and does so in an order that builds upon previously discovered shorter routes, the final table contains the true shortest path between every pair of nodes, assuming no negative cycles exist. An extra check at the end looks for any negative values on the diagonal of the table to detect whether a negative cycle is present anywhere in the graph. This triple-loop approach is simple , turning what would be many separate single-source problems into a single computation.
Comparison
Best for
- Bellman-Ford: Single source, sparse graphs
- Floyd-Warshall: All-pairs, dense graphs (V≤400)
Detects negative cycles
- Bellman-Ford: Yes (reachable from source)
- Floyd-Warshall: Yes (anywhere in graph)
Time
- Bellman-Ford: O(V*E)
- Floyd-Warshall: O(V3)
Space
- Bellman-Ford: O(V)
- Floyd-Warshall: O(V2)
Typical problems:
- Bellman-Ford: Cheapest Flights variants, arbitrage
- Floyd-Warshall: City with smallest number of neighbors within distance., Evaluate division (variants), transitive closure
Code simplicity
- Bellman-Ford: Medium (edge list)
- Floyd-Warshall: Very simple (matrix)
Notes
- Dijkstra is faster when no negatives
- For Bellman-Ford, early termination after no updates in a pass is a nice optimization (still O(V*E) worst case).
- Floyd-Warshall is perfect when V ≤ 400; beyond that you usually need Johnson’s algorithm (Bellman-Ford + Dijkstra).
- Negative cycle detection: Bellman-Ford only detects cycles reachable from the source; Floyd-Warshall catches any cycle in the graph.
- Edge cases: self-loops, disconnected components, negative self-loops (instant cycle).
Conclusion
Bellman-Ford and Floyd-Warshall together solve the entire family of shortest-path problems that Dijkstra cannot touch: any graph with negative edge weights, negative cycle detection, and all-pairs shortest paths.
