# Q3(a) · Dijkstra from t

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2022-ai-final/q3a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2022-ai-final--q3a/

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 ↔

![Original undirected question graph: every edge weight retained; source t](https://deep-learning-study-room.vercel.app/cn/fig/old-ai-cn-2022-11-16-ai-q3a.503e410dd7.svg)

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



$$
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.