# Q7A · Shortest paths · full working

Subject: Computer Networks

Exam: TEE

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

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

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

### TEE practice mock · Q7A. For directed edges A→B=5, A→C=2, B→D=4, C→B=1, C→D=7, D→E=2, C→E=10, use Dijkstra from A to E. Show initialization, each settled vertex, updated distances and final path, and draw the network. [10 mock marks]

#### Answer

## Given

| Edge | Cost |
| --- | --- |
| A→B | 5 |
| A→C | 2 |
| B→D | 4 |
| C→B | 1 |
| C→D | 7 |
| D→E | 2 |
| C→E | 10 |

Source=A; target=E. Edges are directed; do not add reverse edges.

## To find

The path A to E, its total cost and intermediate work.

## Formula and why



$$
d[v]\leftarrow\min(d[v],d[u]+w(u,v))
$$



Use Dijkstra because all weights are nonnegative. Select the smallest unsettled total distance, not the cheapest isolated edge.

Swipe across the diagram to read its labels ↔

![Dijkstra · given directed graph](https://deep-learning-study-room.vercel.app/cn/fig/tee-mock-c-route.93b735aa12.svg)

Diagram: Dijkstra · given directed graph. Labels: Dijkstra · given directed graph | Dijkstra · given directed graph | A | A | B | B | A->B | 5 | C | C | A->C | 2 | D | D | B->D | 4 | C->B | 1 | C->D | 7 | E | E | C->E | 10 | D->E | 2

Read the labels and direction before substituting numbers.

## Step-by-step solution

#### Step 1. Initialize

d[A]=0; every other distance=∞. No predecessors are known.

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Tentative |
| B | ∞ | — | Tentative |
| C | ∞ | — | Tentative |
| D | ∞ | — | Tentative |
| E | ∞ | — | Tentative |

#### Step 2. Settle A at distance 0

Unsettled candidates before selection: A=0, B=∞, C=∞, D=∞, E=∞. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| A→B | ∞ | 0+(5)=5 | Improve to 5; predecessor=A |
| A→C | ∞ | 0+(2)=2 | Improve to 2; predecessor=A |

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 5 | A | Tentative |
| C | 2 | A | Tentative |
| D | ∞ | — | Tentative |
| E | ∞ | — | Tentative |

#### Step 3. Settle C at distance 2

Unsettled candidates before selection: B=5, C=2, D=∞, E=∞. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| C→B | 5 | 2+(1)=3 | Improve to 3; predecessor=C |
| C→D | ∞ | 2+(7)=9 | Improve to 9; predecessor=C |
| C→E | ∞ | 2+(10)=12 | Improve to 12; predecessor=C |

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 3 | C | Tentative |
| C | 2 | A | Settled |
| D | 9 | C | Tentative |
| E | 12 | C | Tentative |

#### Step 4. Settle B at distance 3

Unsettled candidates before selection: B=3, D=9, E=12. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| B→D | 9 | 3+(4)=7 | Improve to 7; predecessor=B |

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 3 | C | Settled |
| C | 2 | A | Settled |
| D | 7 | B | Tentative |
| E | 12 | C | Tentative |

#### Step 5. Settle D at distance 7

Unsettled candidates before selection: D=7, E=12. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| D→E | 12 | 7+(2)=9 | Improve to 9; predecessor=D |

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 3 | C | Settled |
| C | 2 | A | Settled |
| D | 7 | B | Settled |
| E | 9 | D | Tentative |

#### Step 6. Settle E at distance 9

Unsettled candidates before selection: E=9. Select the minimum; ties use alphabetical order.

No outgoing edges to relax.

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 3 | C | Settled |
| C | 2 | A | Settled |
| D | 7 | B | Settled |
| E | 9 | D | Settled |

#### Step 7. Recover the path

Trace backwards: E ← D ← B ← C ← A. Reverse it: A → C → B → D → E.

Edge sum: 2 + 1 + 4 + 2 = 9.

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

#### What this result means

The predecessor table proves which edges make the route. A table containing only the final cost is not the complete working requested.

Swipe across the diagram to read its labels ↔

![Dijkstra · final route and distances](https://deep-learning-study-room.vercel.app/cn/fig/tee-mock-c-route-solution.94d22e6eb0.svg)

Diagram: Dijkstra · final route and distances. Labels: Dijkstra · final route and distances | Dijkstra · final route and distances | A | A | 0 | B | B | 3 | A->B | 5 | C | C | 2 | A->C | 2 | D | D | 7 | B->D | 4 | C->B | 1 | C->D | 7 | E | E | 9 | C->E | 10 | D->E | 2

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