Computer Networks · TEE · papers
Q3(a) · Dijkstra from t
2022-11-16 · AI-only Sem V
Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.
Q3(a). Using Dijkstra’s algorithm, determine the shortest path from t to all nodes. Show all necessary steps; the original graph’s complete edge list is reproduced below. [10 marks]
Original diagram data
| Edge endpoint1 | Endpoint2 | Cost |
|---|---|---|
| z | x | 8 |
| z | y | 12 |
| x | y | 6 |
| x | v | 3 |
| x | w | 6 |
| y | v | 8 |
| y | t | 7 |
| v | t | 4 |
| v | u | 3 |
| v | w | 4 |
| w | u | 3 |
| t | u | 2 |
Answer
Given
The original diagram is undirected. All edge labels are reproduced below. Source = t.
Swipe across the diagram to read its labels ↔
Diagram: Original undirected question graph: every edge weight retained; source t. Labels: Original undirected question graph: every edge weight retained; source t | 8 | 12 | 6 | 3 | 6 | 8 | 7 | 4 | 3 | 4 | 3 | 2 | z | x | y | w | v | t | u
| From | To | Cost |
|---|---|---|
| z | x | 8 |
| z | y | 12 |
| x | y | 6 |
| x | v | 3 |
| x | w | 6 |
| y | v | 8 |
| y | t | 7 |
| v | t | 4 |
| v | u | 3 |
| v | w | 4 |
| w | u | 3 |
| t | u | 2 |
To find
Shortest distance, complete route and predecessor for every node from t.
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 | t | u | v | w | x | y | z |
|---|---|---|---|---|---|---|---|---|
| 0 | Initial | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| t | u←t: 0+2=2; y←t: 0+7=7; v←t: 0+4=4 | 0 | 2 | 4 | ∞ | ∞ | 7 | ∞ |
| u | w←u: 2+3=5 | 0 | 2 | 4 | 5 | ∞ | 7 | ∞ |
| v | x←v: 4+3=7 | 0 | 2 | 4 | 5 | 7 | 7 | ∞ |
| w | No change | 0 | 2 | 4 | 5 | 7 | 7 | ∞ |
| x | z←x: 7+8=15 | 0 | 2 | 4 | 5 | 7 | 7 | 15 |
| y | No change | 0 | 2 | 4 | 5 | 7 | 7 | 15 |
| z | No change | 0 | 2 | 4 | 5 | 7 | 7 | 15 |
Step 2. Read predecessors backwards, then reverse
| Destination | Distance | Previous | Route |
|---|---|---|---|
| t | 0 | — | t |
| u | 2 | t | t → u |
| v | 4 | t | t → v |
| w | 5 | u | t → u → w |
| x | 7 | v | t → v → x |
| y | 7 | t | t → y |
| z | 15 | x | t → v → x → z |
A tie between two equally short paths is valid; this table retains the first predecessor on equal distances.