Question 3 of 6: Shortest-path routing by Dijkstra’s algorithm

Question 3: 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 seven-node undirected network printed with the question, whose ten edges carry the distances read from the figure and listed below. The source node is B.

Find. The least-cost path and its total distance from B to each of A, C, D, E, F and G, showing the label state after every iteration of the algorithm.

[Figure not reproduced: Figure 3.1 — the network of Question 3, redrawn from the examination paper. Edge labels are the given link distances; node B (highlighted) is the source. See the official exam paper.]

Approach. Maintain a set $N'$ of nodes whose least cost from B is already known and a tentative label $D(v)$ for every other node; at each iteration move the unlabelled node of smallest label into $N'$ and relax the edges leaving it, repeating until all seven nodes are in $N'$.

1. Initialise the labels. Put $N' = \{B\}$ and $D(B) = 0$. Every neighbour of B takes the direct edge cost and every other node takes infinity: $$D(A) = 1, \quad D(E) = 5, \quad D(C) = D(D) = D(F) = D(G) = \infty$$ The predecessor of A and of E is B; the others have none yet.
2. Iteration 1: absorb A. The smallest label outside $N'$ is $D(A) = 1$, so $N' = \{B, A\}$. Relaxing the edges out of A, $$D(C) = \min(\infty,\ 1 + 2) = 3, \qquad D(D) = \min(\infty,\ 1 + 2) = 3$$ both by way of A, while $D(E)$ stays at 5 because A does not touch E.
3. Iteration 2: absorb C. C and D are tied at 3; the algorithm may break the tie either way and C is taken first. With $N' = \{B, A, C\}$, relaxing the edges out of C offers $D(D) = \min(3,\ 3+1) = 3$, unchanged, and $$D(F) = \min(\infty,\ 3 + 2) = 5 \text{ by way of } C$$
4. Iteration 3: absorb D. $D(D) = 3$ is now the smallest label outside $N'$, giving $N' = \{B, A, C, D\}$. The edge D–F costs only 1, so $$D(F) = \min(5,\ 3 + 1) = 4 \text{ by way of } D$$ This is the step that repays the bookkeeping: the first route found to F, through C, cost 5, and it is displaced by a cheaper one found two iterations later.
5. Iteration 4: absorb F. With $D(F) = 4$ the set becomes $N' = \{B, A, C, D, F\}$. Relaxing out of F gives $$D(E) = \min(5,\ 4 + 1) = 5, \qquad D(G) = \min(\infty,\ 4 + 3) = 7$$ so E is tied at 5 between the direct edge B–E and the path B–A–D–F–E; the existing predecessor B is kept.
6. Iteration 5: absorb E, then G. $D(E) = 5$ enters $N'$ and the edge E–G, of cost 1, improves G: $$D(G) = \min(7,\ 5 + 1) = 6 \text{ by way of } E$$ G then enters $N'$ at 6 and the algorithm halts with all seven nodes labelled. Note that the cheap E–G edge is only usable once E itself is reached, which is why the expensive direct edge B–E of cost 5 still ends up on the tree.
7. Read off the tree and the paths. Following predecessors back to B gives $$\boxed{B\!-\!A = 1,\ B\!-\!A\!-\!C = 3,\ B\!-\!A\!-\!D = 3,\ B\!-\!A\!-\!D\!-\!F = 4,\ B\!-\!E = 5,\ B\!-\!E\!-\!G = 6}$$ The six tree edges B–A, A–C, A–D, D–F, B–E and E–G total $1+2+2+1+5+1 = 12$, and a tree on seven nodes must have six edges, which is a useful arithmetic check on the work.

The full label history is collected below; each row is the state of the tentative labels at the end of one iteration, with a bracketed predecessor, and a bold entry marks the node absorbed into $N'$ at the start of the next iteration.

Figure 3.2 draws the resulting shortest-path tree on the original network. In a link-state routing protocol such as OSPF or IS-IS this is precisely the computation each router performs on its own copy of the link-state database, and the first hop of each branch — A for four of the six destinations, E for the other two — is what is installed in the forwarding table.