# Q2(a) · Dijkstra from w

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2024-feb-ai-reexam/q2a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2024-feb-ai-reexam--q2a/

Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.

### Q2(a). Using Dijkstra’s algorithm calculate shortest paths from w to all nodes in the original graph. Show all steps; the complete edge list is 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 = w.

Swipe across the diagram to read its labels ↔

![Original undirected question graph: every edge weight retained; source w](https://deep-learning-study-room.vercel.app/cn/fig/old-ai-cn-2024-02-06-ai-q2a.60ea5488ef.svg)

Diagram: Original undirected question graph: every edge weight retained; source w. Labels: Original undirected question graph: every edge weight retained; source w | 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 w.

### 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 | t | u | v | w | x | y | z |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | Initial | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | ∞ |
| w | u←w: 0+3=3; x←w: 0+6=6; v←w: 0+4=4 | ∞ | 3 | 4 | 0 | 6 | ∞ | ∞ |
| u | t←u: 3+2=5 | 5 | 3 | 4 | 0 | 6 | ∞ | ∞ |
| v | y←v: 4+8=12 | 5 | 3 | 4 | 0 | 6 | 12 | ∞ |
| t | No change | 5 | 3 | 4 | 0 | 6 | 12 | ∞ |
| x | z←x: 6+8=14 | 5 | 3 | 4 | 0 | 6 | 12 | 14 |
| y | No change | 5 | 3 | 4 | 0 | 6 | 12 | 14 |
| z | No change | 5 | 3 | 4 | 0 | 6 | 12 | 14 |

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

| Destination | Distance | Previous | Route |
| --- | --- | --- | --- |
| t | 5 | u | w → u → t |
| u | 3 | w | w → u |
| v | 4 | w | w → v |
| w | 0 | — | w |
| x | 6 | w | w → x |
| y | 12 | v | w → v → y |
| z | 14 | x | w → x → z |

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