Computer Networks · TEE · papers
Q7(a) · Dijkstra graph
2024-02-06 · 2022-23
Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.
Q7(a). Determine the shortest path and shortest distance from source vertex A to every other vertex in the following graph using Dijkstra’s Algorithm. Illustrate step-by-step procedure and draw shortest path table. [10 marks]
Original diagram data
| From | To | Cost |
|---|---|---|
| A | B | 3 |
| A | C | 5 |
| B | C | 9 |
| B | D | 8 |
| B | E | 6 |
| C | E | 3 |
| D | E | 10 |
| D | F | 3 |
| E | F | 5 |
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 2024 original question graph. Labels: dijkstra 2024 original question graph | 3 | 5 | 9 | 8 | 6 | 3 | 10 | 3 | 5 | A | B | C | D | E | F
| From | To | Cost |
|---|---|---|
| A | B | 3 |
| A | C | 5 |
| B | C | 9 |
| B | D | 8 |
| B | E | 6 |
| C | E | 3 |
| D | E | 10 |
| D | F | 3 |
| E | F | 5 |
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; C←A: 0+5=5 | 0 | 3 | 5 | ∞ | ∞ | ∞ |
| B | D←B: 3+8=11; E←B: 3+6=9 | 0 | 3 | 5 | 11 | 9 | ∞ |
| C | E←C: 5+3=8 | 0 | 3 | 5 | 11 | 8 | ∞ |
| E | F←E: 8+5=13 | 0 | 3 | 5 | 11 | 8 | 13 |
| D | No change | 0 | 3 | 5 | 11 | 8 | 13 |
| F | No change | 0 | 3 | 5 | 11 | 8 | 13 |
Step 2. Read predecessors backwards, then reverse
| Destination | Distance | Previous | Route |
|---|---|---|---|
| A | 0 | — | A |
| B | 3 | A | A → B |
| C | 5 | A | A → C |
| D | 11 | B | A → B → D |
| E | 8 | C | A → C → E |
| F | 13 | E | A → C → E → F |
A tie between two equally short paths is valid; this table retains the first predecessor on equal distances.