Bellman–Ford, negative cycles, shortest paths in DAGs

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Why does Dijkstra fail with negative edges? from Lesson 6.3.1
• Topological order exists for? from Lesson 6.1.3
• DP time formula? from Lesson 5.1.1

1 · The Hook

🎣

Currency exchange, energy that can be gained on downhill paths, profits as negative costs: some graphs have negative edges. Bellman–Ford handles them by relaxing every edge again and again, and it can tell when a negative cycle makes "shortest" meaningless. On DAGs a single pass in topological order is enough.

2 · Predict First

🤔

A shortest path (no negative cycle) never repeats a vertex. At most how many edges can it have in a graph with V vertices?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

V − 1: a simple path visits each vertex once.

Bellman–Ford

dist[s] = 0; all others ∞
repeat V - 1 times:
    for each edge (u, v) in a fixed order: RELAX(u, v)
for each edge (u, v):
    if dist[u] + w(u, v) < dist[v]: report "negative cycle reachable from s"

After round i, every vertex whose shortest path uses ≤ i edges has its correct distance (a DP on the number of edges). Θ(VE). It may converge earlier, depending on edge order.

Worked example

Vertices s, t, x, y, z; edges in this order: s→t 6, s→y 7, t→x 5, t→y 8, t→z −4, x→t −2, y→x −3, y→z 9, z→x 7, z→s 2.

Final: t 2, x 4, y 7, z −2; the check pass finds no improvement, so there is no negative cycle.

Negative cycles

If a cycle of negative total weight is reachable, distances can be pushed down forever: no shortest path exists, and the V-th pass still improves something.

Shortest paths in a DAG

Topologically sort, then relax the out-edges of each vertex once, in topological order. Θ(V + E), negative edges allowed (a DAG has no cycles at all).

4 · Visual

DAG shortest paths from s (topological order r, s, t, x, y, z)

edges: r->s 5, r->t 3, s->t 2, s->x 6, t->x 7, t->y 4, t->z 2,
       x->y -1, x->z 1, y->z -2

vertex:   r    s    t    x    y    z
dist:     inf  0    2    6    5    3
          (r is not reachable from s)

5 · Worked Examples

Example 1 Easy

Bellman–Ford on a graph with 10 vertices: how many relaxation rounds (before the check)?

Solution

V − 1 = 9.

Example 2 Medium

In the DAG above, what is the shortest distance from s to z?

Solution

s → x 6, x → y 5, y → z 3 (s → t → z gives 4).

Example 3 GATE

Directed cycle a → b 1, b → c −1, c → a −1. Does Bellman–Ford from a report a negative cycle?

Solution

Cycle weight 1 − 1 − 1 = −1 < 0: yes.

6 · GATE Traps

⚠️

• Bellman–Ford: V − 1 rounds, then one extra check for negative cycles.
• Distances after round i depend on the edge order; the final answer does not.
• DAG shortest paths work with negative edges in Θ(V + E).
• Negative edges ≠ negative cycle; only the latter makes shortest paths undefined.

7 · Memory Hook

🧠

"Relax everything V − 1 times; if it still improves, there is a negative cycle."

8 · Connect the Dots

Bellman–Ford answers one source. The last lesson of the phase finds shortest paths between all pairs at once with a three-line DP: Floyd–Warshall.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markBellman–Ford

In the lesson's Bellman–Ford example, final dist[z]?

Numerical answer: ________

Q2NAT2 marksRound 1

In the lesson's example (same edge order), what is dist[t] after round 1?

Numerical answer: ________

Q3NAT2 marksDAG paths

In the lesson's DAG, shortest distance from s to y?

Numerical answer: ________

Q4MCQ1 markCost

Bellman–Ford runs in:

• (A) Θ(V³)
• (B) Θ(VE)
• (C) Θ(E log V)
• (D) Θ(V + E)

Q5MSQ2 marksFacts

Which are true?

• (A) Bellman–Ford can detect a negative cycle reachable from the source.
• (B) A shortest simple path has at most V − 1 edges.
• (C) DAG shortest paths need non-negative weights.
• (D) Bellman–Ford works with negative edge weights.

10 · Rule Card

• Bellman–Ford: V − 1 rounds relaxing all edges; extra pass detects negative cycles; Θ(VE).
• Round i fixes paths with ≤ i edges (DP on edge count).
• DAG: relax in topological order once; Θ(V + E); negative edges fine.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

Bellman–Ford algorithmrelaxation roundsnegative-cycle detectionDP on number of edgesDAG shortest paths in topological order

12 · Answer Vault