# Q3(a) · Dijkstra from u

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2023-jan-ai-reexam/q3a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2023-jan-ai-reexam--q3a/

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

### Q3(a). Using Dijkstra’s algorithm calculate shortest paths from u to all nodes, showing every step. The original undirected graph’s edges are reproduced below. [10 marks]

### Original diagram data

| Edge endpoint1 | Endpoint2 | Cost |
| --- | --- | --- |
| u | v | 4 |
| u | w | 3 |
| u | x | 5 |
| v | w | 1 |
| v | x | 8 |
| x | w | 7 |
| x | y | 7 |
| w | y | 6 |
| w | z | 7 |
| y | z | 7 |

### Answer

### Given

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

Swipe across the diagram to read its labels ↔

![Original undirected question graph: every edge weight retained; source u](https://deep-learning-study-room.vercel.app/cn/fig/old-ai-cn-2023-01-27-ai-q3a.e2a89263bf.svg)

Diagram: Original undirected question graph: every edge weight retained; source u. Labels: Original undirected question graph: every edge weight retained; source u | 4 | 3 | 5 | 1 | 8 | 7 | 7 | 6 | 7 | 7 | u | v | x | w | y | z

| From | To | Cost |
| --- | --- | --- |
| u | v | 4 |
| u | w | 3 |
| u | x | 5 |
| v | w | 1 |
| v | x | 8 |
| x | w | 7 |
| x | y | 7 |
| w | y | 6 |
| w | z | 7 |
| y | z | 7 |

### To find

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

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

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

| Destination | Distance | Previous | Route |
| --- | --- | --- | --- |
| u | 0 | — | u |
| v | 4 | u | u → v |
| w | 3 | u | u → w |
| x | 5 | u | u → x |
| y | 9 | w | u → w → y |
| z | 10 | w | u → w → z |

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