Shortest-Path Routing by Dijkstra’s Algorithm: 22-Elec-B4 Information Technology Networks, December 2014, Q2

Question 2: 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 printed with the question, read directly from the examination drawing: seven nodes and eleven edges, with the link costs tabulated below.

The network of Question 2. Node A is the source; edge labels are link costs. Eleven edges connect the seven nodes.

Given data — link costs
Edge	Cost	Edge	Cost	Edge	Cost
A–B	5	C–D	1	E–F	6
A–C	1	C–E	1	E–G	1
A–D	3	C–F	2	F–G	3
B–E	2	D–F	1

Find. The least-cost path from A to each of B, C, D, E, F and G, together with its cost, obtained by an explicit execution of Dijkstra’s algorithm.

Approach. Maintain a set $N$ of nodes whose shortest distance is already known and a label $D(v)$ for every other node; at each iteration move the unlabelled node of smallest label into $N$, then relax its neighbours using $D(v) \leftarrow \min\{D(v),\, D(w) + c(w,v)\}$.

Initialise. Put the source into the permanent set, $N = \{\mathrm{A}\}$, and label every other node with its direct link cost from A, or infinity where no direct link exists: $$D(\mathrm{B}) = 5, \quad D(\mathrm{C}) = 1, \quad D(\mathrm{D}) = 3, \quad D(\mathrm{E}) = D(\mathrm{F}) = D(\mathrm{G}) = \infty.$$
Iteration 1 — absorb C. The smallest label among unlabelled nodes is $D(\mathrm{C}) = 1$, so C joins the permanent set and its neighbours are relaxed. Through C we reach D at $1 + 1 = 2$ (better than the direct 3), E at $1 + 1 = 2$, and F at $1 + 2 = 3$. Node C is a hub of cost-1 links, which is why it dominates the whole solution: $$N = \{\mathrm{A,C}\}, \quad D(\mathrm{B}) = 5, \ D(\mathrm{D}) = 2, \ D(\mathrm{E}) = 2, \ D(\mathrm{F}) = 3, \ D(\mathrm{G}) = \infty.$$
Iteration 2 — absorb D. D and E are tied at 2; the algorithm may take either, and taking D first changes nothing about the final answer. Relaxing through D offers F at $2 + 1 = 3$, which merely ties the label F already holds. Hence $$N = \{\mathrm{A,C,D}\}, \quad D(\mathrm{B}) = 5, \ D(\mathrm{E}) = 2, \ D(\mathrm{F}) = 3, \ D(\mathrm{G}) = \infty.$$
Iteration 3 — absorb E. E enters at cost 2 and is the pivotal relaxation of the problem. Through E, node B improves from 5 to $2 + 2 = 4$, so the direct A–B link is abandoned; node G is reached for the first time at $2 + 1 = 3$; and F is offered $2 + 6 = 8$, which is rejected. Thus $$N = \{\mathrm{A,C,D,E}\}, \quad D(\mathrm{B}) = 4, \ D(\mathrm{F}) = 3, \ D(\mathrm{G}) = 3.$$
Iterations 4 and 5 — absorb F, then G. F and G are tied at 3. Absorbing F offers G a route at $3 + 3 = 6$, which loses to the label of 3 that G already carries, so nothing changes; G is then absorbed at 3 and offers B nothing. $$N = \{\mathrm{A,C,D,E,F,G}\}, \quad D(\mathrm{B}) = 4.$$
Iteration 6 — absorb B and terminate. B is the last node, entering at 4. Every node is now permanent, so the algorithm halts and the labels are the true shortest-path costs: $$\boxed{D(\mathrm{B}) = 4,\ D(\mathrm{C}) = 1,\ D(\mathrm{D}) = 2,\ D(\mathrm{E}) = 2,\ D(\mathrm{F}) = 3,\ D(\mathrm{G}) = 3}$$

Tracing each node back through the predecessor that last improved its label gives the routes themselves, which together form the shortest-path tree rooted at A shown below. Two observations are worth recording for the examiner. First, the expensive A–B edge of cost 5 and the E–F edge of cost 6 are never used — every optimal route avoids them. Second, node F is reached at cost 3 by two genuinely tied routes, A–C–F and A–C–D–F; the shortest-path tree is therefore not unique, though the cost vector is.

The shortest-path tree rooted at A (heavy lines). The A–B and E–F edges carry no traffic; the F branch is drawn via C, the tied alternative running A–C–D–F at the same cost of 3.

Question 2 — shortest paths from A
Destination	Least-cost path	Cost	Next hop from A
B	A–C–E–B	4	C
C	A–C	1	C
D	A–C–D	2	C
E	A–C–E	2	C
F	A–C–F or A–C–D–F	3	C
G	A–C–E–G	3	C

Topic. Link-state routing and Dijkstra’s shortest-path algorithm.

Key relations. Relaxation $D(v) \leftarrow \min\{D(v),\, D(w)+c(w,v)\}$; the greedy invariant that the smallest tentative label in the frontier is already final; complexity $O(|V|^{2})$ with a linear scan, $O(|E| \log |V|)$ with a binary heap.

Why this works. The algorithm is correct because all link costs are non-negative. Suppose the node $v$ with the smallest tentative label were not final; then some cheaper path to $v$ must leave the permanent set through a different frontier node $u$, but $u$ has a label at least as large as $v$, and appending further non-negative edges can only increase the total. The contradiction shows the greedy choice is safe, which is exactly why Dijkstra fails on negative-cost links and why link-state protocols such as OSPF and IS-IS advertise only non-negative metrics. Each router floods its adjacencies, every router thereby holds the same topology database, and each independently runs this computation to fill its own forwarding table — which is why the last column of the results table, the next hop, is all a router actually stores.

Common pitfall. Two dominate. The first is finalising a node without relaxing all of its neighbours, which leaves stale labels — here it would leave B at 5 instead of 4. The second is presenting only the final answer: the question awards no marks unless the iterations are shown, so the permanent set and the label vector must be written out at every step. A third is to overlook ties and claim a unique tree when two equal-cost routes exist, as they do for F.

Source. Leon-Garcia and Widjaja, Communication Networks, ch. 7 (packet-switching networks, shortest-path routing); Kurose and Ross, Computer Networking, ch. 5.2 (link-state routing).

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

Question 2: Shortest-Path Routing by Dijkstra’s Algorithm (25 marks)