Q5(c) · Bellman-Ford example

Answer

Definition. Bellman–Ford computes single-source shortest paths by repeatedly relaxing every edge. It supports negative edge weights and detects reachable negative cycles.

Simple meaning. Har edge ko baar-baar relax; negative edge chalega, negative cycle problem hai.

Understand it step by step

1. Initialize source 0 and all other distances ∞.
2. Relax every directed edge, in a stated order, for at most V−1 full passes, where V is the number of vertices. A shortest simple path uses at most V−1 edges when no relevant negative cycle exists.
3. In the in-place convention used here, an update is immediately available to later edges in the same pass. Different edge orders can therefore produce different intermediate tables while converging to the same valid final distances.
4. If a full pass makes no change, all distances have stabilized and the algorithm may stop early.
5. A further improvement on a reachable edge after V−1 passes signals a reachable negative cycle. Destinations reachable from such a cycle need not have a finite shortest distance.

Yaad rakho: Pass = all edges once. Negative edge ≠ negative cycle.

Given

Directed edge	Weight
A→B	4
A→C	5
B→C	-2
C→D	3

To find

The shortest route and cost, with complete passes and a negative-cycle check.

Formula and why

LaTeX: d[v]\leftarrow\min(d[v],d[u]+w(u,v))

Bellman–Ford permits negative edges. We use the listed order with in-place updates; do not mix this with a table that reads only the previous pass.

Swipe across the diagram to read its labels ↔

Diagram: Bellman–Ford · given directed graph. Labels: Bellman–Ford · given directed graph | Bellman–Ford · given directed graph | A | A | B | B | A->B | 4 | C | C | A->C | 5 | B->C | -2 | D | D | C->D | 3

Step-by-step solution

Step 1. Initialize

4 vertices → at most 3 main passes. d[A]=0; every other distance=∞. Use the listed edge order and immediate (in-place) updates.

Step 2. Pass 1: relax every edge

Edge	Old d[target]	Candidate via source	New d[target]	Decision
A→B	∞	0+(4)=4	4	Update; predecessor=A
A→C	∞	0+(5)=5	5	Update; predecessor=A
B→C	5	4+(-2)=2	2	Update; predecessor=B
C→D	∞	2+(3)=5	5	Update; predecessor=C

Vertex	A	B	C	D
End-of-pass distance	0	4	2	5
Predecessor	—	A	B	C

Step 3. Pass 2: relax every edge

Edge	Old d[target]	Candidate via source	New d[target]	Decision
A→B	4	0+(4)=4	4	No improvement
A→C	2	0+(5)=5	2	No improvement
B→C	2	4+(-2)=2	2	No improvement
C→D	5	2+(3)=5	5	No improvement

Step 4. Stop after an unchanged pass

This entire pass changed no distance. Further identical relaxation passes will not improve anything.

Step 5. Recover and total the path

Backward predecessors: D ← C ← B ← A. Forward route: A → B → C → D.

Cost = (4) + (-2) + (3) = 5. No edge can now improve its destination label.

Final answer: A → B → C → D; shortest cost=5.