# Q4(a) · Dijkstra from u

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2023-ai-partial/q4a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2023-ai-partial--q4a/

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

### Q4(a). Using Dijkstra’s algorithm, calculate the shortest path from u to all nodes in the given undirected graph. Show every step. The complete original 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 = 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-11-22-ai-q4a.23319ec754.svg)

Diagram: Original undirected question graph: every edge weight retained; source u. Labels: Original undirected question graph: every edge weight retained; source u | 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 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 | t | u | v | w | x | y | z |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | Initial | ∞ | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| u | v←u: 0+3=3; w←u: 0+3=3; t←u: 0+2=2 | 2 | 0 | 3 | 3 | ∞ | ∞ | ∞ |
| t | y←t: 2+7=9 | 2 | 0 | 3 | 3 | ∞ | 9 | ∞ |
| v | x←v: 3+3=6 | 2 | 0 | 3 | 3 | 6 | 9 | ∞ |
| w | No change | 2 | 0 | 3 | 3 | 6 | 9 | ∞ |
| x | z←x: 6+8=14 | 2 | 0 | 3 | 3 | 6 | 9 | 14 |
| y | No change | 2 | 0 | 3 | 3 | 6 | 9 | 14 |
| z | No change | 2 | 0 | 3 | 3 | 6 | 9 | 14 |

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

| Destination | Distance | Previous | Route |
| --- | --- | --- | --- |
| t | 2 | u | u → t |
| u | 0 | — | u |
| v | 3 | u | u → v |
| w | 3 | u | u → w |
| x | 6 | v | u → v → x |
| y | 9 | t | u → t → y |
| z | 14 | x | u → v → x → z |

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