# Q5(c) · Bellman-Ford example

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2024-final/q5c

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2024-final--q5c/

Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.

### Q5(c). Explain Bellman Ford algorithm for finding shortest path from source node to destination node with the help of an example. [10 marks]

### 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.

#### Practical example

A→B=4 and B→C=−2 can give A→C cost 2. A negative edge is not itself a negative cycle; a cycle requires a route returning to an earlier vertex.

Bellman–Ford repeatedly relaxes all edges and can handle negative weights. It uses up to V−1 passes and an additional improvement check for reachable negative cycles. Dijkstra settles the smallest tentative vertex and requires nonnegative weights for its standard correctness guarantee.

**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



$$
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 ↔

![Bellman–Ford · given directed graph](https://deep-learning-study-room.vercel.app/cn/fig/bellman-1.1bf4232fcf.svg)

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

Read the labels and direction before substituting numbers.

## 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.

#### What this result means

Negative weights are a general graph-exercise feature. RIP hop counts and OSPF link costs are not negative in the ordinary routing protocols studied here.