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

Question 5: 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.

Given. The undirected weighted graph below, read directly from the examination page. Ten edges carry ten distance labels:

Find. The shortest distance and the corresponding path from source node F to each of A, B, C, D, E and G, with the algorithm's working shown at every iteration.

[Figure not reproduced. See the official exam paper.]

Approach. Maintain a set $N'$ of nodes whose shortest distance is already final, a tentative label $D(v)$ for every other node, and a predecessor $p(v)$ recording the node through which the current best path reaches $v$. Repeatedly move the unlabelled node of smallest tentative distance into $N'$ and relax its edges. Ties are broken alphabetically, which affects only the order of the table, never the final distances.

1. Initialise. $D(F) = 0$, $p(F) = -$, and $D(v) = \infty$ for every other node, with $N' = \{F\}$. Relaxing F's four edges gives the first row: $D(C) = 2$, $D(D) = 1$, $D(E) = 1$, $D(G) = 3$, each with predecessor F, while A and B remain at infinity.
2. Iteration 1 — add D. The smallest tentative label is 1, shared by D and E; taking D first, $N' = \{F, D\}$. Relaxing D's edges: $D(A) = 1 + 2 = 3$ via D, an improvement on infinity; $D(C) = 1 + 1 = 2$ ties the existing label of 2, so the label and its predecessor F are left unchanged.
3. Iteration 2 — add E. The smallest remaining label is $D(E) = 1$, so $N' = \{F, D, E\}$. Relaxing E's edges: $D(B) = 1 + 5 = 6$ via E; and $D(G) = 1 + 1 = 2$, which improves on the direct F–G label of 3, so G's label falls to 2 and its predecessor changes from F to E.
4. Iteration 3 — add C. C and G now tie at 2; taking C, $N' = \{F, D, E, C\}$. Relaxing C's edges offers $D(A) = 2 + 2 = 4$, which is worse than the standing 3, so nothing changes. This step is where the algorithm's guarantee is visible: no later discovery can improve a label already made permanent, because every remaining route out of $N'$ starts at a distance at least as large.
5. Iteration 4 — add G. $N' = \{F, D, E, C, G\}$; both of G's neighbours are already permanent, so no label changes.
6. Iteration 5 — add A. $D(A) = 3$ is now the smallest remaining, so $N' = \{F, D, E, C, G, A\}$. Relaxing A's edges gives $D(B) = 3 + 1 = 4$ via A, an improvement on the 6 obtained through E, so B's label falls to 4 and its predecessor becomes A.
7. Iteration 6 — add B. The last node enters with $D(B) = 4$, all seven nodes are permanent, and the algorithm halts.

The full tableau. Each cell shows the tentative distance and, in parentheses, the predecessor; a bold entry is the label being made permanent in that step.

Reading the paths off the predecessors. Following $p(\cdot)$ back to F from each node gives

Two features of this particular network are worth pointing out to a marker. First, node C has two shortest paths of equal length: the direct edge F–C costs 2, and F–D–C costs $1 + 1 = 2$ as well. Dijkstra's algorithm keeps whichever it relaxed first — here the direct edge, discovered at initialisation — and the tie is genuine, so a candidate who reports F–D–C is equally correct. Second, the direct edge F–G is not on the shortest path to G: routing through E costs $1 + 1 = 2$ against the direct 3. This is the standard warning against confusing a one-hop route with a short one, and it is the reason link-state protocols such as OSPF and IS-IS run this algorithm rather than counting hops as RIP does. The six tree edges total $1 + 1 + 2 + 1 + 2 + 1 = 8$ units.