Computer Networks · TEE · papers
Q6(a) · Dijkstra six-node graph
2025-02-19 · 2023-24 / 2024-25
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 ↔
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
LaTeX: 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.