Shortest-path routing (25 marks): 22-Elec-B4 Information Technology Networks, December 2015, Q5

Question 5 — Shortest-path routing (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. An undirected network of seven nodes A to G and ten weighted edges, read from the figure printed with the question:

Given data — edge lengths
Edge	Length	Edge	Length	Edge	Length
A–B	1	C–D	1	E–F	1
A–C	2	C–F	2	E–G	1
A–D	2	D–F	1	F–G	3
B–E	5	Source node: B

Find. The least-cost path and its total length from node B to each of A, C, D, E, F and G, obtained by a correct execution of Dijkstra's algorithm with the working shown at every iteration.

[Figure not reproduced: The network as printed with the question: seven nodes, ten undirected edges, with the length marked on each edge. See the official exam paper.]

Approach. Maintain a set $S$ of nodes whose shortest distance is already known, together with a tentative label $d(v)$ for every other node; at each iteration move the unlabelled node of smallest label into $S$ and relax its edges.

Initialise. Put the source in the permanent set and label every other node with the direct edge from B if one exists, otherwise infinity: $$S=\{B\},\quad d(B)=0,\quad d(A)=1,\quad d(E)=5,\quad d(C)=d(D)=d(F)=d(G)=\infty.$$ Only A and E adjoin B, so only those two labels are finite at the start.
Iteration 1 — make A permanent. The smallest tentative label is $d(A)=1$, so A joins $S$. Relaxing A's edges, the routes B → A → C and B → A → D each cost $1+2=3$, improving both labels from infinity: $$d(C)\leftarrow3,\qquad d(D)\leftarrow3,\qquad S=\{B,A\}.$$
Iteration 2 — make C permanent. C and D are tied at 3; the algorithm may take either, and taking C first gives $S=\{B,A,C\}$. Relaxing C's edges, the route through C to D would cost $3+1=4$, which does not improve $d(D)=3$, while F is reached for the first time: $$d(F)\leftarrow3+2=5,\qquad d(D)\ \text{unchanged at }3.$$ This is a useful check that the tie was harmless — D keeps the label it already had.
Iteration 3 — make D permanent. With $d(D)=3$ the smallest remaining, D joins $S$. Its edge to F now offers a cheaper route, so the tentative label improves: $$d(F)\leftarrow\min(5,\ 3+1)=4\quad\text{via }B\rightarrow A\rightarrow D\rightarrow F.$$
Iteration 4 — make F permanent. $d(F)=4$ is now the smallest label outstanding. Relaxing F gives $$d(E)\leftarrow\min(5,\ 4+1)=5,\qquad d(G)\leftarrow4+3=7.$$ The label on E is a genuine tie: the direct edge B–E and the path B → A → D → F → E both cost 5, so the shortest-path tree is not unique. Keeping the incumbent is the standard convention.
Iteration 5 — make E permanent. E enters with $d(E)=5$, and its edge of length 1 to G improves the last outstanding label: $$d(G)\leftarrow\min(7,\ 5+1)=6\quad\text{via }B\rightarrow E\rightarrow G.$$ Note that the F–G edge of length 3, which produced the earlier label of 7, ends up on no shortest path at all.
Iteration 6 — make G permanent and stop. G joins $S$ with $d(G)=6$; every node is now permanent, so the algorithm terminates: $$\boxed{d(A)=1,\ d(C)=3,\ d(D)=3,\ d(F)=4,\ d(E)=5,\ d(G)=6}$$

Dijkstra iteration table — tentative labels after each step (permanent labels in bold)
Step	Node made permanent	Permanent set S	d(A)	d(C)	d(D)	d(E)	d(F)	d(G)
0	B (source)	{B}	1	∞	∞	5	∞	∞
1	A (1)	{B,A}	1	3	3	5	∞	∞
2	C (3)	{B,A,C}	1	3	3	5	5	∞
3	D (3)	{B,A,C,D}	1	3	3	5	4	∞
4	F (4)	{B,A,C,D,F}	1	3	3	5	4	7
5	E (5)	{B,A,C,D,F,E}	1	3	3	5	4	6
6	G (6)	all	1	3	3	5	4	6

Tracing each predecessor back to the source recovers the routes themselves, which are what a router would actually install in its forwarding table.

The resulting shortest-path tree rooted at B, drawn heavy over the original network. The C-F and F-G edges carry no shortest path.

Question 5 — shortest paths from node B
Destination	Least cost	Route	Note
A	1	B → A	direct edge
C	3	B → A → C	—
D	3	B → A → D	tied with C for the second selection
E	5	B → E	ties with B → A → D → F → E, also 5
F	4	B → A → D → F	—
G	6	B → E → G	ties with B → A → D → F → E → G, also 6

Topic. Link-state routing and the shortest-path problem: Dijkstra's algorithm, the shortest-path tree, and how a router turns that tree into a forwarding table.

Key relations. Relaxation $d(v)\leftarrow\min\bigl(d(v),\,d(u)+w(u,v)\bigr)$ applied to every neighbour $v$ of the node $u$ just made permanent; the selection rule “make permanent the unlabelled node of smallest tentative label”; termination after $|V|-1$ selections; complexity $O(|E|\log|V|)$ with a binary heap, $O(|V|^{2})$ with a linear scan.

Why this works. The correctness argument is worth being able to state, because it explains the one restriction the algorithm has. When a node $u$ is selected it carries the smallest tentative label of any node outside $S$; any alternative path to $u$ must leave $S$ at some point, and the first node it meets outside $S$ already has a label at least as large as $d(u)$. Since edge weights are non-negative, the remainder of that path can only add to the cost, so no route can beat $d(u)$ and the label may safely be frozen. That argument fails outright if a negative edge exists — which is why link-state protocols such as OSPF and IS-IS insist on non-negative metrics. In practice each router floods its own link states, so every router holds the same map, runs this same computation rooted at itself, and installs the first hop of each tree branch as its next hop.

Common pitfall. Relaxing the edges of a node that has not yet been made permanent, which quietly turns the algorithm into something else and can give wrong answers; and stopping as soon as the label on a node stops changing rather than when the node is selected. On this particular network the trap is the E label: it is tempting to overwrite the incumbent 5 with the equal 5 offered through F, which is harmless numerically but obscures the fact that two shortest-path trees exist. Note also that the F–G edge of length 3 is never used, a reminder that shortest-path trees routinely leave edges idle.

Source. Leon-Garcia and Widjaja, Communication Networks, 2nd ed., §7.4 (shortest-path routing algorithms); Kurose and Ross, Computer Networking: A Top-Down Approach, 8th ed., §5.2.1; Tanenbaum and Wetherall, Computer Networks, 5th ed., §5.2.2.

Question 5 of 5: Shortest-path routing (25 marks)

Question 5 — Shortest-path routing (25 marks)