# Q7A · Shortest paths · full working

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/mocks/tee-mock-b/q7a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/mocks/tee-mock-b--q7a/

TEE · 100 attempted marks · solutions for every choice · current syllabus 702AI0C023

### TEE practice mock · Q7A. For directed edges A→B=4, A→C=5, B→C=−2, B→D=6, C→D=2, D→E=3, C→E=8, use Bellman–Ford from A to E. Show the declared edge order, each pass, final distances and path; explain the negative-cycle check. [10 mock marks]

#### Answer

## Given

| Directed edge | Weight |
| --- | --- |
| A→B | 4 |
| A→C | 5 |
| B→C | -2 |
| B→D | 6 |
| C→D | 2 |
| D→E | 3 |
| C→E | 8 |

## 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/tee-mock-b-route.720ccc32b6.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 | B->D | 6 | C->D | 2 | E | E | C->E | 8 | D->E | 3

Read the labels and direction before substituting numbers.

## Step-by-step solution

#### Step 1. Initialize

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

| Vertex | A | B | C | D | E |
| --- | --- | --- | --- | --- | --- |
| End-of-pass distance | 0 | 4 | 2 | 4 | 7 |
| Predecessor | — | A | B | C | D |

#### 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 |
| B→D | 4 | 4+(6)=10 | 4 | No improvement |
| C→D | 4 | 2+(2)=4 | 4 | No improvement |
| D→E | 7 | 4+(3)=7 | 7 | No improvement |
| C→E | 7 | 2+(8)=10 | 7 | No improvement |

| Vertex | A | B | C | D | E |
| --- | --- | --- | --- | --- | --- |
| End-of-pass distance | 0 | 4 | 2 | 4 | 7 |
| Predecessor | — | A | B | C | D |

#### 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: E ← D ← C ← B ← A. Forward route: A → B → C → D → E.

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

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

#### 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/tee-mock-b-route-solution.f6bae119c4.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 | 4 | A->B | 4 | C | C | 2 | A->C | 5 | B->C | -2 | D | D | 4 | B->D | 6 | C->D | 2 | E | E | 7 | C->E | 8 | D->E | 3

Highlighted final shortest path, with source-to-vertex distance labels.