Computer Networks · TEE · papers
Q7A · Bellman–Ford intermediate steps
Re-exam · 4 February 2026
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))](https://deep-learning-study-room.vercel.app/cn/math/651d18e4e3d7619d.svg)
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.
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.
Source: Re-exam · 4 February 2026, original question paper page 3. Original marks retained; solution independently authored.