# Q7(a) · Dijkstra graph

Subject: Computer Networks

Exam: TEE

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

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

Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.

### Q7(a). Determine the shortest path and shortest distance from source vertex A to every other vertex in the following graph using Dijkstra’s Algorithm. Illustrate step-by-step procedure and draw shortest path table. [10 marks]

### Original diagram data

| From | To | Cost |
| --- | --- | --- |
| A | B | 3 |
| A | C | 5 |
| B | C | 9 |
| B | D | 8 |
| B | E | 6 |
| C | E | 3 |
| D | E | 10 |
| D | F | 3 |
| E | F | 5 |

### Answer

### Given

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

Swipe across the diagram to read its labels ↔

![dijkstra 2024 original question graph](https://deep-learning-study-room.vercel.app/cn/fig/old-dijkstra-2024.b1cf42a96f.svg)

Diagram: dijkstra 2024 original question graph. Labels: dijkstra 2024 original question graph | 3 | 5 | 9 | 8 | 6 | 3 | 10 | 3 | 5 | A | B | C | D | E | F

| From | To | Cost |
| --- | --- | --- |
| A | B | 3 |
| A | C | 5 |
| B | C | 9 |
| B | D | 8 |
| B | E | 6 |
| C | E | 3 |
| D | E | 10 |
| D | F | 3 |
| E | F | 5 |

### To find

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

### 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 | A | B | C | D | E | F |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | Initial | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| A | B←A: 0+3=3; C←A: 0+5=5 | 0 | 3 | 5 | ∞ | ∞ | ∞ |
| B | D←B: 3+8=11; E←B: 3+6=9 | 0 | 3 | 5 | 11 | 9 | ∞ |
| C | E←C: 5+3=8 | 0 | 3 | 5 | 11 | 8 | ∞ |
| E | F←E: 8+5=13 | 0 | 3 | 5 | 11 | 8 | 13 |
| D | No change | 0 | 3 | 5 | 11 | 8 | 13 |
| F | No change | 0 | 3 | 5 | 11 | 8 | 13 |

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

| Destination | Distance | Previous | Route |
| --- | --- | --- | --- |
| A | 0 | — | A |
| B | 3 | A | A → B |
| C | 5 | A | A → C |
| D | 11 | B | A → B → D |
| E | 8 | C | A → C → E |
| F | 13 | E | A → C → E → F |

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