Bellman-Ford in Coding Interviews: Shortest Paths with Negative Edges and Limited Stops

Most candidates learn Dijkstra's algorithm and stop there. But a whole family of interview questions breaks Dijkstra: graphs with negative edge weights, questions about negative cycles, and the popular "cheapest flight with at most K stops." The tool for these is Bellman-Ford, a simpler and more flexible algorithm that every candidate should be able to write from memory. The core idea: relaxation, repeated Bellman-Ford keeps a distance array, initialized to infinity except for the source at zero. It then loops over every edge and "relaxes" it: if dist[u] + w < dist[v], update dist[v]. After one pass, all shortest paths that use at most one edge are correct. After k passes, all shortest paths using at most k edges are correct. Since a shortest simple path has at most V - 1 edges, V - 1 passes are enough. def bellman_ford(n, edges, src): INF = float('inf') dist = [INF] * n dist[src] = 0 for _ in range(n - 1): changed = False for u, v, w in edges: if dist[u] != INF and dist[u] + w < dist[v]: dist[v] = dist[u] + w changed = True if not changed: break # one more pass detects negative cycles for u, v, w in edges: if dist[u] != INF and dist[u] + w < dist[v]: return None # negative cycle reachable return dist Complexity: O(V * E) time and O(V) space. Slower than Dijkstra's O(E log V), but it handles negative weights and detects negative cycles. Why Dijkstra fails with negative edges Dijkstra finalizes a node the first time it is popped from the heap, assuming no later path can be shorter. A negative edge discovered later can violate that assumption. Being able to explain this in one or two sentences is a common interview checkpoint. The "at most K stops" variant In "Cheapest Flights Within K Stops," you want the cheapest path from src to dst using at most K + 1 edges. Bellman-Ford's structure fits perfectly: run exactly K + 1 passes. The subtle point is to relax from a copy of the previous pass's distances, so a single pass cannot chain multiple edges together. def cheapest_flight(n, flights, src, dst, k): INF = float('inf') dist = [INF] * n dist[src] = 0 for _ in range(k + 1): prev = dist[:] for u, v, w in flights: if prev[u] != INF and prev[u] + w < dist[v]: dist[v] = prev[u] + w return -1 if dist[dst] == INF else dist[dst] Forgetting the copy is the most frequent bug interviewers see in this problem. Other places it shows up - Currency arbitrage: take negative logarithms of exchange rates; an arbitrage opportunity becomes a negative cycle. - Systems of difference constraints: constraints like x_j - x_i <= c map to edges, and Bellman-Ford finds a feasible assignment or proves none exists. - SPFA, a queue-based optimization, often runs faster in practice, though its worst case is the same. How to choose in an interview - Non-negative weights, single source: Dijkstra. - Negative weights or cycle detection: Bellman-Ford. - Edge-count limit: Bellman-Ford with K + 1 passes, or BFS by levels. - All pairs on a small graph: Floyd-Warshall. Stating this decision out loud before coding shows the interviewer you understand trade-offs, not just one memorized algorithm. Keeping these distinctions straight while you code under time pressure is tough. Linkjob AI (https://linkjob.ai) provides real-time help during job interviews and technical interviews, helping you structure your reasoning as you work through a problem. It is most useful alongside genuine practice. Takeaway: when edges can be negative or the number of edges is limited, Bellman-Ford is the algorithm to reach for.