# Q7A · Bellman–Ford · full directed graph

Subject: Computer Networks

Exam: M2

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

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

Actual TEE paper · current-M2 matching parts; original marks

### Actual PYQ. 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. [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.