Question 4 of 5: Shortest-Path Routing by Dijkstra's Algorithm

Question 4: Shortest-Path Routing by Dijkstra's Algorithm (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

[Figure not reproduced: Figure 4.1 — The network of Question 4, redrawn from the examination paper: seven nodes and ten undirected edges with the printed distances. Node F is the source. See the official exam paper.]

Approach. Maintain a set $N$ of nodes whose distance is final and a tentative label $D(v)$ for every other node; at each iteration move the unlabelled node of smallest tentative distance into $N$, then relax every edge out of it, recording the predecessor whenever a label improves.

1. Initialise from the source. Set $D(\text{F}) = 0$ and $N = \{\text{F}\}$. Every neighbour of F takes the length of its direct edge and every other node takes infinity:
   $$D(\text{C}) = 2,\quad D(\text{D}) = 1,\quad D(\text{E}) = 1,\quad D(\text{G}) = 3,\quad D(\text{A}) = D(\text{B}) = \infty$$

   The predecessor of each labelled node is F.

2. Iteration 1 — add D. The smallest tentative label is 1, held by both D and E; ties may be broken arbitrarily and D is taken first. With $D(\text{D}) = 1$ made permanent, relax D's edges: A improves from $\infty$ to $1 + 2 = 3$ with predecessor D, and C is offered $1 + 1 = 2$, which merely ties its existing label of 2, so no change is recorded. This tie is real and is worth stating in the answer: F–C and F–D–C are both of length 2.

3. Iteration 2 — add E. The smallest remaining label is 1 at E. Relaxing E's edges gives B its first finite label, $1 + 5 = 6$ with predecessor E, and improves G from 3 to $1 + 1 = 2$ with predecessor E — the two-hop route F–E–G beats the direct edge F–G of length 3.

4. Iterations 3 and 4 — add C, then G. Both now carry the label 2. Making C permanent offers A the value $2 + 2 = 4$, which does not beat the existing 3, so nothing changes; making G permanent offers nothing new, since both of its neighbours are already permanent. Neither iteration alters a label, which is the normal behaviour once the frontier has passed a node.

5. Iteration 5 — add A. The smallest remaining label is 3 at A. Relaxing A's edges improves B from 6 to $3 + 1 = 4$, with predecessor A: the long direct edge B–E of length 5 is beaten by going the long way round through D and A.

6. Iteration 6 — add B, and the algorithm terminates. B enters with 4 and $N$ now contains all seven nodes, so every label is final. Collecting the work into one table, where a dash marks a node already made permanent:

   Iteration	Node added (final $D$)	$D(\text{A})$	$D(\text{B})$	$D(\text{C})$	$D(\text{D})$	$D(\text{E})$	$D(\text{G})$
   Init	F (0)	$\infty$	$\infty$	2 (F)	1 (F)	1 (F)	3 (F)
   1	D (1)	3 (D)	$\infty$	2 (F)	—	1 (F)	3 (F)
   2	E (1)	3 (D)	6 (E)	2 (F)	—	—	2 (E)
   3	C (2)	3 (D)	6 (E)	—	—	—	2 (E)
   4	G (2)	3 (D)	6 (E)	—	—	—	—
   5	A (3)	—	4 (A)	—	—	—	—
   6	B (4)	—	—	—	—	—	—

   The letter in brackets is the predecessor recorded with each label, which is what turns the distances into paths.

7. Read the paths off the predecessors. Following each predecessor back to F gives the routes, and their lengths reproduce the final labels exactly:
   $$\boxed{\begin{aligned} \text{F} \rightarrow \text{A} &= \text{F-D-A} = 1 + 2 = 3, &\quad \text{F} \rightarrow \text{B} &= \text{F-D-A-B} = 1 + 2 + 1 = 4,\\ \text{F} \rightarrow \text{C} &= \text{F-C} = 2, &\quad \text{F} \rightarrow \text{D} &= \text{F-D} = 1,\\ \text{F} \rightarrow \text{E} &= \text{F-E} = 1, &\quad \text{F} \rightarrow \text{G} &= \text{F-E-G} = 1 + 1 = 2. \end{aligned}}$$

   The six predecessor edges form the shortest-path tree rooted at F, of total weight $1 + 1 + 2 + 2 + 1 + 1 = 8$; this tree, not the distance list, is what a router would install as its forwarding state.

   Figure 4.2 — The shortest-path tree rooted at F drawn heavy over the original graph: F–C, F–D, F–E, D–A, A–B and E–G. The unused edges A–C, C–D, B–E and F–G are shown thin.
8. Sanity-check the result. Three checks cost nothing and catch the usual slips. The tree has six edges for six non-source nodes and no cycle, as any shortest-path tree must; the two edges the algorithm rejected are each demonstrably worse than the route chosen, since B–E offers B a length of $1+5 = 6$ against the 4 actually found and F–G offers G a length of 3 against the 2 actually found; and every label is non-decreasing in the order the nodes were made permanent (0, 1, 1, 2, 2, 3, 4), which is the property that makes Dijkstra's greedy choice valid on non-negative weights.