# Q6(a) · Dijkstra six-node graph

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2025-feb-reexam/q6a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2025-feb-reexam--q6a/

Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.

### Q6(a). Consider the following network diagram comprising 6 nodes. Find the shortest path and shortest distance using Dijkstra’s Algorithm from A to every other node. Show all the intermediate steps. Show the table with shortest distance and previous node for all 6 nodes. [10 marks]

### Original diagram data

| From | To | Cost |
| --- | --- | --- |
| A | B | 3 |
| A | D | 7 |
| B | D | 5 |
| B | E | 5 |
| D | E | 4 |
| D | F | 2 |
| E | F | 1 |
| E | C | 8 |
| F | C | 3 |

### Answer

### Given

The original diagram is undirected. All edge labels are reproduced below. Source = A.

Swipe across the diagram to read its labels ↔

![dijkstra 2025 original question graph](https://deep-learning-study-room.vercel.app/cn/fig/old-dijkstra-2025.c24a5141a1.svg)

Diagram: dijkstra 2025 original question graph. Labels: dijkstra 2025 original question graph | 3 | 7 | 5 | 5 | 4 | 2 | 1 | 8 | 3 | A | B | C | D | E | F

| From | To | Cost |
| --- | --- | --- |
| A | B | 3 |
| A | D | 7 |
| B | D | 5 |
| B | E | 5 |
| D | E | 4 |
| D | F | 2 |
| E | F | 1 |
| E | C | 8 |
| F | C | 3 |

### To find

Shortest distance, complete route and predecessor for every node from A.

### Formula and why



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



Relaxation replaces a tentative route when going through u is cheaper. Dijkstra settles the unvisited node of least tentative distance. Nonnegative edge costs make the settled distance final. Equal-distance nodes may be settled in either order.

### Step 1. Initialize and relax

| Pass / settled node | Strict improvements | A | B | C | D | E | F |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | Initial | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| A | B←A: 0+3=3; D←A: 0+7=7 | 0 | 3 | ∞ | 7 | ∞ | ∞ |
| B | E←B: 3+5=8 | 0 | 3 | ∞ | 7 | 8 | ∞ |
| D | F←D: 7+2=9 | 0 | 3 | ∞ | 7 | 8 | 9 |
| E | C←E: 8+8=16 | 0 | 3 | 16 | 7 | 8 | 9 |
| F | C←F: 9+3=12 | 0 | 3 | 12 | 7 | 8 | 9 |
| C | No change | 0 | 3 | 12 | 7 | 8 | 9 |

### Step 2. Read predecessors backwards, then reverse

| Destination | Distance | Previous | Route |
| --- | --- | --- | --- |
| A | 0 | — | A |
| B | 3 | A | A → B |
| C | 12 | F | A → D → F → C |
| D | 7 | A | A → D |
| E | 8 | B | A → B → E |
| F | 9 | D | A → D → F |

A tie between two equally short paths is valid; this table retains the first predecessor on equal distances.