220: Shortest Paths II: Bellman-Ford, Floyd-Warshall, 0-1 BFS, and DAG Paths

Learning outcomes

By the end of this lesson, you can:

explain and apply bellman-ford in a realistic implementation;
explain and apply negative cycles in a realistic implementation;
explain and apply floyd-warshall in a realistic implementation;
explain and apply 0-1 bfs in a realistic implementation;
explain and apply dag shortest paths in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before you read, retrieve one concrete example from a previous project where the same kind of constraint mattered: perhaps a graph with an unusual weight domain, a dependency chain, or a failure case that made the default algorithm unsafe. The point is not to memorize another set of names. It is to make a defensible choice both in an interview-sized problem and in a production data-processing problem. Start from the constraints, then select the algorithm that makes those constraints easiest to satisfy and explain.

Terminology

Bellman-Ford: Relax every edge V-1 times; any further improvement reachable from the source indicates a negative cycle. The repeated passes allow a shortest path to grow by one edge per pass. The guard that the source-side endpoint is already reachable is essential: an unrelated negative cycle elsewhere in the graph must not be reported as a problem for this source.
Negative cycles: A reachable negative cycle means no finite shortest path for vertices whose paths can exploit the cycle indefinitely. The distance can be reduced again on every trip around the cycle, so a useful implementation must distinguish unreachable vertices, finite distances, and vertices affected by a reachable negative cycle.
Floyd-Warshall: Dynamic programming over allowed intermediate vertices computes all-pairs shortest paths in O(V³) time and O(V²) space, practical for small/dense graphs. Its central invariant is that after processing an intermediate vertex, the table contains the best routes that use only the intermediate vertices considered so far.
0-1 BFS: When edge weights are only 0 or 1, use a deque: zero-weight relaxations go to the front and one-weight relaxations to the back, achieving O(V+E). The algorithm relies on this restricted weight domain; replacing a weight with 2 or 10 without changing the algorithm breaks the ordering argument.
DAG shortest paths: Topologically process a DAG and relax outgoing edges once; negative weights are fine because there are no cycles and dependencies are ordered. A topological order ensures every predecessor has been finalized before a vertex is used to relax its outgoing edges.
Algorithm selection: Choose from graph size, density, number of sources/queries, weight restrictions, and negative-cycle semantics rather than memorizing a hierarchy of “better” algorithms. The best choice is the one whose assumptions match the input and whose failure behavior matches the product requirement.

Mental model

Treat Shortest Paths II: Bellman-Ford, Floyd-Warshall, 0-1 BFS, and DAG Paths as a design problem with observable inputs, outputs, invariants, and failure modes. Different graph structures and weight domains enable specialized shortest-path algorithms; recognizing those constraints is more valuable than forcing every problem into Dijkstra. A strong implementation makes its assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to prove why the design is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. For example, ask whether a path may contain negative edges, whether all pairs or only one source are needed, whether weights are limited to 0 and 1, and whether a reachable negative cycle has a defined business meaning. Then choose the mechanism that enforces those conditions. This makes both the implementation and its review easier: the invariant is not hidden inside the algorithm name.

Deep dive

1. Bellman-Ford

The problem Bellman-Ford addresses is straightforward: a graph may contain negative edge weights, so the nonnegative-weight assumption behind Dijkstra is unavailable. Bellman-Ford relaxes every edge V-1 times; any further improvement reachable from the source indicates a negative cycle. A relaxation replaces distance[to] when the known route to from plus the edge weight is cheaper.

The useful invariant is that after the pass that considers paths with at most k edges, every shortest path whose route uses at most k edges has been accounted for. If no negative cycle is reachable from the source, a simple shortest path uses at most V-1 edges, which is why V-1 passes are enough. An additional pass is the diagnostic pass. If it still improves a reachable destination, some route can keep getting cheaper.

Complexity O(VE) is slower than algorithms specialized for nonnegative or restricted weights, but Bellman-Ford supports negative edges and gives a direct way to reason about reachable negative cycles. In production code, use a sufficiently wide numeric representation and choose an infinity sentinel that cannot overflow when an edge weight is added. Never relax from an unreachable vertex: adding to an infinity sentinel can manufacture a false route.

Decision rule: Use bellman-ford deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Confirm that the graph size makes O(VE) acceptable and that the caller actually needs negative-edge support or negative-cycle detection.

2. Negative cycles

The difficult case is not merely finding a cycle. A reachable negative cycle means no finite shortest path for vertices whose paths can exploit the cycle indefinitely. Every additional circuit lowers the route cost, so returning the current numeric distance as if it were final is misleading. Detection and propagation requirements depend on the problem: one caller may only need a boolean, while another must mark every vertex reachable from the negative cycle as having an undefined shortest distance.

The source matters. A negative cycle that cannot be reached from the chosen start vertex does not affect that single-source query. After Bellman-Ford's normal passes, inspect relaxable edges whose source endpoint has a finite distance. Those edges identify the region that can still improve; a subsequent reachability traversal can propagate the affected status when the API needs per-vertex answers. Keep “unreachable” separate from “affected by a negative cycle”; they have different meanings and should not share a sentinel accidentally.

Decision rule: Use negative cycles deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Define what the caller observes when a cycle is reachable: an error, a special status, or a set of affected destinations. That decision belongs in the output contract, not as an undocumented detail of the implementation.

3. Floyd-Warshall

When the question is “what is the shortest route between every pair of vertices?”, running a single-source algorithm repeatedly may be less clear than maintaining one table. Floyd-Warshall uses dynamic programming over allowed intermediate vertices to compute all-pairs shortest paths in O(V³) time and O(V²) space, practical for small or dense graphs.

Let distance[i][j] represent the best known cost from i to j. Initially it contains zero for i === j, each direct edge weight, and infinity when no direct route is known. For each intermediate vertex k, update distance[i][j] with the cheaper of the existing route and the route through k: distance[i][k] + distance[k][j]. The invariant is that after k is processed, every table entry is optimal among routes whose internal vertices come from the processed set. The update must be based on the current table, but the in-place form is safe when the loop ordering follows the standard k, i, j structure.

Parallel edges require initialization with the minimum direct weight, not whichever edge happens to be read last. As with Bellman-Ford, infinity must be guarded before arithmetic. A negative cycle can be detected after the computation when some distance[v][v] is negative. That indicates that paths involving that vertex can keep decreasing, but applications that need affected pairs still have to propagate which (i, j) routes can pass through such a vertex.

Decision rule: Use floyd-warshall deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. O(V²) storage and O(V³) time make it a poor fit for a very large sparse graph, but a strong fit for a small graph with many pair queries.

4. 0-1 BFS

Some graphs have a stronger property than merely having nonnegative weights: every edge costs exactly 0 or 1. When edge weights are only 0 or 1, use a deque. A zero-weight relaxation goes to the front because it does not increase the current distance; a one-weight relaxation goes to the back because it belongs to the next distance layer. Under that restriction, the approach achieves O(V+E).

The deque is not a cosmetic replacement for a queue. Its placement rule maintains the ordering needed for shortest-distance processing. Each successful relaxation moves a vertex to a position consistent with its new distance, and the restricted weights prevent arbitrary jumps in priority. If the input contains any other weight, validate or reject it rather than silently applying 0-1 BFS. For duplicate edges, relaxing normally handles the cheaper route, while stale deque entries should not be allowed to corrupt the result.

Decision rule: Use 0-1 bfs deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State the 0-or-1 weight precondition at the boundary and test it; the O(V+E) claim depends on that precondition.

5. DAG shortest paths

In a directed acyclic graph, the absence of cycles gives a simpler dependency order. Topologically process a DAG and relax outgoing edges once; negative weights are fine because there are no cycles and dependencies are ordered. By the time a vertex is processed, every possible predecessor has already had an opportunity to improve it.

The invariant is that a processed vertex has its final shortest distance from the source. A topological sort can be produced before relaxation, or the graph can be traversed in a way that establishes the same order. If topological sorting cannot include every vertex, the input is not a DAG and the algorithm's guarantee does not apply. Unreachable vertices remain at infinity and should not be used as arithmetic sources.

Decision rule: Use dag shortest paths deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. This is often the clearest option for dependency graphs, build plans, and other acyclic workflows, but only after acyclicity has been established.

6. Algorithm selection

Choose from graph size, density, number of sources/queries, weight restrictions, and negative-cycle semantics rather than memorizing a hierarchy of “better” algorithms. For one source with negative edges, Bellman-Ford is the direct general-purpose choice. For many pair queries on a small graph, Floyd-Warshall may pay its cubic preprocessing cost once. For 0/1 weights, 0-1 BFS uses a property that a general algorithm would leave unused. For a DAG, topological order removes the need for repeated reconsideration.

The selection is a contract decision. Ask what the graph guarantees, what the output must say about unreachable or undefined routes, and whether the data is sparse or dense. Then record the relevant complexity: Bellman-Ford is O(VE), Floyd-Warshall is O(V³) time and O(V²) space, and both 0-1 BFS and DAG shortest paths can be O(V+E) with their required constraints. A benchmark is useful only after these semantic constraints are correct.

Worked example

Consider an interview-sized problem and a production data-processing problem. The learner should reason from constraints rather than memorize a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which concept above owns each failure mode. The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes edge cases and algorithm assumptions much harder to inspect.

type Edge = readonly [to: number, weight: number];
type Graph = readonly Edge[][];

function bfs(graph: Graph, start: number): number[] {
  const distance = Array(graph.length).fill(-1);
  const queue = [start];
  distance[start] = 0;
  for (let i = 0; i < queue.length; i++) {
    const node = queue[i]!;
    for (const [next] of graph[node]!) {
      if (distance[next] !== -1) continue;
      distance[next] = distance[node] + 1;
      queue.push(next);
    }
  }
  return distance;
}

This small BFS is intentionally a reference point rather than an implementation of the weighted algorithms above. It shows the familiar “discover once, then expand” shape and makes the limitation visible: it measures edges, not arbitrary weights. That is why selecting an algorithm from the graph's weight domain matters. A weighted shortest-path implementation must maintain the appropriate relaxation invariant instead of copying this queue pattern blindly.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. For the graph itself, also include an unreachable vertex, a duplicate edge, a negative edge where the selected algorithm permits it, and a reachable negative cycle where the contract needs to define the result. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For graph processing, that means checking whether vertices and edge endpoints are valid, whether weights fit the chosen numeric representation, whether graph size is bounded, and whether a long-running computation needs cancellation or a resource limit. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. Those general rules apply here too: a graph received over the network needs validation, and a negative-cycle status should not be inferred from a client-side display or an unchecked sentinel.

Guided lab

Solve the same small weighted graph with Bellman-Ford and Floyd-Warshall, add a negative cycle, then implement a 0-1 BFS case and a DAG shortest-path case. Build an algorithm-selection table. For each implementation, record the weight assumptions, the output for an unreachable vertex, the negative-cycle behavior, the time and space complexity, and the invariant that justifies the update order.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the invalid-input test, use a case that violates the selected algorithm's precondition, such as a weight other than 0 or 1 for 0-1 BFS or a cyclic graph for DAG paths. For the edge-case test, use an unreachable vertex, parallel edges, a single-vertex graph, or a reachable negative cycle as appropriate. The goal is to inspect not only the numeric answer but also whether the result status is honest.

Edge cases and failure modes

Bellman-Ford: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Also test negative edges, an unreachable negative cycle, and a reachable negative cycle; verify that an unreachable source endpoint is never used in a relaxation.
Negative cycles: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Distinguish a cycle that is reachable from the source from one that is not, and verify propagation when affected vertices must be reported.
Floyd-Warshall: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include parallel edges, missing self-routes, negative edges, and negative diagonal entries that reveal a negative cycle.
0-1 BFS: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify both zero- and one-weight placement, and reject or otherwise define behavior for weights outside the allowed domain.
DAG shortest paths: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include negative weights, disconnected vertices, parallel edges, and a graph that fails the acyclicity check.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For graph algorithms, common debugging symptoms are especially informative. A distance that improves after the supposed final pass suggests a reachable negative cycle or a broken invariant. A result that changes when edge input order changes suggests incorrect initialization or incomplete relaxation. A 0-1 BFS result that is wrong only for certain weights often means the input violated the 0/1 precondition. A DAG result that leaves plausible routes undiscovered usually points to an invalid or incomplete topological order.

Reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. Log or inspect the relaxation that first changes a distance unexpectedly, including the source endpoint's current status and the edge weight. That evidence is more useful than printing only the final distance table.

Interview questions

What problem does Bellman-Ford solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Negative cycles solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Floyd-Warshall solve, and what trade-off or failure mode would make you choose a different approach?
What problem does 0-1 BFS solve, and what trade-off or failure mode would make you choose a different approach?
What problem does DAG shortest paths solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do more than name the algorithm. State the input guarantee, the output semantics for unreachable or undefined paths, the invariant that supports correctness, and the relevant time and space cost. This is usually where the difference between memorization and engineering judgment becomes visible.

Checkpoint

Without notes, explain Shortest Paths II: Bellman-Ford, Floyd-Warshall, 0-1 BFS, and DAG Paths to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. Be explicit about why the chosen algorithm's assumptions hold and what the caller should receive when they do not.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.