# Q7A · Dijkstra with all intermediate steps

Subject: Computer Networks

Exam: TEE

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

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/tee-paper-final--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 between these nodes and their corresponding positive weights are given in the table below. Using Dijkstra’s Algorithm: (i) Determine the shortest path from source A to destination G. (ii) Compute the shortest distance. (iii) Show all intermediate steps, including initialization and selection of the minimum-distance node for each iteration. (iv) Illustrate the original topology and final shortest path with edge distances. Directed edges: A→B=4, A→C=2, B→C=5, B→D=10, C→D=3, C→E=4, D→E=1, D→F=2, E→F=3, F→G=5. [10 marks]

#### Answer

## Given

| Edge | Cost |
| --- | --- |
| A→B | 4 |
| A→C | 2 |
| B→C | 5 |
| B→D | 10 |
| C→D | 3 |
| C→E | 4 |
| D→E | 1 |
| D→F | 2 |
| E→F | 3 |
| F→G | 5 |

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

## To find

The path A to G, 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/dijkstra-pyq.ffe6efac11.svg)

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

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 |
| F | ∞ | — | Tentative |
| G | ∞ | — | Tentative |

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

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

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

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

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

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

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| C→D | ∞ | 2+(3)=5 | Improve to 5; predecessor=C |
| C→E | ∞ | 2+(4)=6 | Improve to 6; predecessor=C |

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

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

Unsettled candidates before selection: B=4, D=5, E=6, F=∞, G=∞. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| B→C | 2 | 4+(5)=9 | Already settled; retain |
| B→D | 5 | 4+(10)=14 | Retain 5 |

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

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

Unsettled candidates before selection: D=5, E=6, F=∞, G=∞. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| D→E | 6 | 5+(1)=6 | Retain 6 (equal cost) |
| D→F | ∞ | 5+(2)=7 | Improve to 7; predecessor=D |

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 4 | A | Settled |
| C | 2 | A | Settled |
| D | 5 | C | Settled |
| E | 6 | C | Tentative |
| F | 7 | D | Tentative |
| G | ∞ | — | Tentative |

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

Unsettled candidates before selection: E=6, F=7, G=∞. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| E→F | 7 | 6+(3)=9 | Retain 7 |

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 4 | A | Settled |
| C | 2 | A | Settled |
| D | 5 | C | Settled |
| E | 6 | C | Settled |
| F | 7 | D | Tentative |
| G | ∞ | — | Tentative |

#### Step 7. Settle F at distance 7

Unsettled candidates before selection: F=7, G=∞. Select the minimum; ties use alphabetical order.

| Edge | Old distance | Candidate | Decision |
| --- | --- | --- | --- |
| F→G | ∞ | 7+(5)=12 | Improve to 12; predecessor=F |

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 4 | A | Settled |
| C | 2 | A | Settled |
| D | 5 | C | Settled |
| E | 6 | C | Settled |
| F | 7 | D | Settled |
| G | 12 | F | Tentative |

#### Step 8. Settle G at distance 12

Unsettled candidates before selection: G=12. Select the minimum; ties use alphabetical order.

No outgoing edges to relax.

| Vertex | Distance from A | Predecessor | State |
| --- | --- | --- | --- |
| A | 0 | — | Settled |
| B | 4 | A | Settled |
| C | 2 | A | Settled |
| D | 5 | C | Settled |
| E | 6 | C | Settled |
| F | 7 | D | Settled |
| G | 12 | F | Settled |

#### Step 9. Recover the path

Trace backwards: G ← F ← D ← C ← A. Reverse it: A → C → D → F → G.

Edge sum: 2 + 3 + 2 + 5 = 12.

**Final answer:** A → C → D → F → G; cost=12.

#### 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/dijkstra-pyq-solution.d92888ba14.svg)

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

Highlighted final route: A→C→D→F→G; total cost 12.

Source: Final · 5 December 2025, original question paper page 3. Original marks retained; solution independently authored.