# Q7A · Bellman–Ford intermediate steps

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/tee-paper-reexam/q7a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/tee-paper-reexam--q7a/

TEE · Actual TEE paper · all questions · current syllabus 702AI0C023

### Actual PYQ · Q7A. Consider a network topology consisting of nodes A, B, C, D, E, F, and G. The directed edges and weights are given below. Using Bellman–Ford: (i) Determine the shortest path from A to G. (ii) Compute its shortest distance. (iii) Show all intermediate steps, including edge relaxation at each iteration. (iv) Illustrate the original topology and the final shortest path with edge distances clearly marked. Directed edges: A→B=7, A→C=6, A→D=5, B→E=−2, D→C=−2, C→B=−2, C→E=1, E→G=5, D→F=3, F→G=4. [10 marks]

#### Answer

## Given

| Directed edge | Weight |
| --- | --- |
| A→B | 7 |
| A→C | 6 |
| A→D | 5 |
| B→E | -2 |
| D→C | -2 |
| C→B | -2 |
| C→E | 1 |
| E→G | 5 |
| D→F | 3 |
| F→G | 4 |

## 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-pyq.8245b97635.svg)

Diagram: Bellman–Ford · given directed graph. Labels: Bellman–Ford · given directed graph | Bellman–Ford · given directed graph | A | A | B | B | A->B | 7 | C | C | A->C | 6 | D | D | A->D | 5 | E | E | B->E | -2 | C->B | -2 | C->E | 1 | D->C | -2 | F | F | D->F | 3 | G | G | E->G | 5 | F->G | 4

Read the labels and direction before substituting numbers.

## Step-by-step solution

#### Step 1. Initialize

7 vertices → at most 6 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+(7)=7 | 7 | Update; predecessor=A |
| A→C | ∞ | 0+(6)=6 | 6 | Update; predecessor=A |
| A→D | ∞ | 0+(5)=5 | 5 | Update; predecessor=A |
| B→E | ∞ | 7+(-2)=5 | 5 | Update; predecessor=B |
| D→C | 6 | 5+(-2)=3 | 3 | Update; predecessor=D |
| C→B | 7 | 3+(-2)=1 | 1 | Update; predecessor=C |
| C→E | 5 | 3+(1)=4 | 4 | Update; predecessor=C |
| E→G | ∞ | 4+(5)=9 | 9 | Update; predecessor=E |
| D→F | ∞ | 5+(3)=8 | 8 | Update; predecessor=D |
| F→G | 9 | 8+(4)=12 | 9 | No improvement |

| Vertex | A | B | C | D | E | F | G |
| --- | --- | --- | --- | --- | --- | --- | --- |
| End-of-pass distance | 0 | 1 | 3 | 5 | 4 | 8 | 9 |
| Predecessor | — | C | D | A | C | D | E |

#### Step 3. Pass 2: relax every edge

| Edge | Old d[target] | Candidate via source | New d[target] | Decision |
| --- | --- | --- | --- | --- |
| A→B | 1 | 0+(7)=7 | 1 | No improvement |
| A→C | 3 | 0+(6)=6 | 3 | No improvement |
| A→D | 5 | 0+(5)=5 | 5 | No improvement |
| B→E | 4 | 1+(-2)=-1 | -1 | Update; predecessor=B |
| D→C | 3 | 5+(-2)=3 | 3 | No improvement |
| C→B | 1 | 3+(-2)=1 | 1 | No improvement |
| C→E | -1 | 3+(1)=4 | -1 | No improvement |
| E→G | 9 | -1+(5)=4 | 4 | Update; predecessor=E |
| D→F | 8 | 5+(3)=8 | 8 | No improvement |
| F→G | 4 | 8+(4)=12 | 4 | No improvement |

| Vertex | A | B | C | D | E | F | G |
| --- | --- | --- | --- | --- | --- | --- | --- |
| End-of-pass distance | 0 | 1 | 3 | 5 | -1 | 8 | 4 |
| Predecessor | — | C | D | A | B | D | E |

#### Step 4. Pass 3: relax every edge

| Edge | Old d[target] | Candidate via source | New d[target] | Decision |
| --- | --- | --- | --- | --- |
| A→B | 1 | 0+(7)=7 | 1 | No improvement |
| A→C | 3 | 0+(6)=6 | 3 | No improvement |
| A→D | 5 | 0+(5)=5 | 5 | No improvement |
| B→E | -1 | 1+(-2)=-1 | -1 | No improvement |
| D→C | 3 | 5+(-2)=3 | 3 | No improvement |
| C→B | 1 | 3+(-2)=1 | 1 | No improvement |
| C→E | -1 | 3+(1)=4 | -1 | No improvement |
| E→G | 4 | -1+(5)=4 | 4 | No improvement |
| D→F | 8 | 5+(3)=8 | 8 | No improvement |
| F→G | 4 | 8+(4)=12 | 4 | No improvement |

| Vertex | A | B | C | D | E | F | G |
| --- | --- | --- | --- | --- | --- | --- | --- |
| End-of-pass distance | 0 | 1 | 3 | 5 | -1 | 8 | 4 |
| Predecessor | — | C | D | A | B | D | E |

#### Step 5. Stop after an unchanged pass

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

#### Step 6. Recover and total the path

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

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

**Final answer:** A → D → C → B → E → G; shortest cost=4.

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

Swipe across the diagram to read its labels ↔

![Bellman–Ford · final route and distances](https://deep-learning-study-room.vercel.app/cn/fig/bellman-pyq-solution.9ae8451e95.svg)

Diagram: Bellman–Ford · final route and distances. Labels: Bellman–Ford · final route and distances | Bellman–Ford · final route and distances | A | A | 0 | B | B | 1 | A->B | 7 | C | C | 3 | A->C | 6 | D | D | 5 | A->D | 5 | E | E | -1 | B->E | -2 | C->B | -2 | C->E | 1 | D->C | -2 | F | F | 8 | D->F | 3 | G | G | 4 | E->G | 5 | F->G | 4

Highlighted route A→D→C→B→E→G, cost 5−2−2−2+5=4.

Source: Re-exam · 4 February 2026, original question paper page 3. Original marks retained; solution independently authored.