Shortest-Path Routing by Dijkstra's Algorithm: 22-Elec-B4 Information Technology Networks, December 2016, Q5

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. An undirected weighted network of seven nodes and ten edges, taken from the printed figure as listed in the table below, with node F as the source.

Given data — edge distances read from the figure
Edge	Distance	Edge	Distance
A–B	1	C–F	2
A–C	2	D–F	1
A–D	2	E–F	1
B–E	5	E–G	1
C–D	1	F–G	3

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

[Figure not reproduced: The network of Question 5 as printed, with the ten edge distances. Node F is the source. See the official exam paper.]

Approach. Maintain a tentative distance and predecessor for every node. Repeatedly remove the unvisited node of least tentative distance, declare it permanent, and relax each of its edges — that is, replace a neighbour's tentative distance whenever going via the newly permanent node is cheaper. Because every distance is non-negative, a node's label is final the moment it is removed, which is the guarantee that makes the single pass correct.

Initialise the labels. The source is at distance zero and every other node is unreachable so far: $$d(F)=0,\qquad d(A)=d(B)=d(C)=d(D)=d(E)=d(G)=\infty,$$ with the permanent set $S=\{\,\}$ and every predecessor undefined.
Iteration 1 — make F permanent and relax its edges. F is the only node with a finite label, so it is removed first and $S=\{F\}$. F's neighbours are C, D, E and G, giving $$d(C)=0+2=2,\quad d(D)=0+1=1,\quad d(E)=0+1=1,\quad d(G)=0+3=3,$$ each with predecessor F. A and B are still unreachable.
Iteration 2 — make D permanent. The smallest unvisited label is 1, held jointly by D and E; ties may be broken arbitrarily and D is taken first. With $S=\{F,D\}$ and $d(D)=1$, relax D's edges to A and C: $$d(A)=\min(\infty,\;1+2)=3\ \text{via D},\qquad d(C)=\min(2,\;1+1)=2\ \text{unchanged}.$$ The C label ties exactly — F–C direct and F–D–C both cost 2 — so the existing predecessor is kept and the tie is noted.
Iteration 3 — make E permanent. E now holds the smallest unvisited label, 1, so $S=\{F,D,E\}$. Relaxing E's edges to B and G: $$d(B)=\min(\infty,\;1+5)=6\ \text{via E},\qquad d(G)=\min(3,\;1+1)=2\ \text{via E — improved}.$$ This is the one relaxation that overwrites an earlier label: the direct edge F–G of length 3 is beaten by the two-hop route F–E–G of length 2, which is exactly the behaviour a “show all work” question is looking for.
Iteration 4 — make C permanent. The unvisited labels are now A = 3, B = 6, C = 2 and G = 2; C and G tie at 2 and C is taken first. With $S=\{F,D,E,C\}$, relax C's remaining edge to A: $$d(A)=\min(3,\;2+2)=3\ \text{unchanged},$$ so nothing improves and the algorithm moves on.
Iteration 5 — make G permanent. G is removed at distance 2, giving $S=\{F,D,E,C,G\}$. Both of G's neighbours, E and F, are already permanent, so there is nothing to relax. Its final path is read back through its predecessor chain as F–E–G.
Iteration 6 — make A permanent and improve B. A is removed at distance 3, so $S=\{F,D,E,C,G,A\}$. A's unvisited neighbour is B: $$d(B)=\min(6,\;3+1)=4\ \text{via A — improved}.$$ The five-length edge B–E is abandoned in favour of the longer-looking but cheaper route F–D–A–B, the second relaxation of the run.
Iteration 7 — make B permanent and terminate. B is removed at distance 4 and every node is now in S, so the algorithm halts. The order in which nodes were made permanent is $$\boxed{F,\ D,\ E,\ C,\ G,\ A,\ B\quad\text{at distances }0,\,1,\,1,\,2,\,2,\,3,\,4.}$$ The labels are non-decreasing along that order, which is the standard correctness check on a Dijkstra run.
Read the paths back through the predecessors. Following each node's predecessor chain to the source gives F–D–A for A, F–D–A–B for B, F–C for C, F–D for D, F–E for E and F–E–G for G. These six edges — F–D, F–C, F–E, E–G, D–A and A–B — form the shortest-path tree drawn heavy in the second figure, and their labels sum to 13, the total cost of routing one packet from F to every other node.

The shortest-path tree rooted at F, drawn heavy over the original network. The six tree edges are F–D, F–C, F–E, E–G, D–A and A–B; the unused edges B–E, C–D, F–G and A–C are the ones every relaxation rejected.

The iteration table below is the compact form usually expected in the answer book: one row per iteration, one column per node, with a permanent label struck once the node joins S.

Dijkstra label table — source F (bold = made permanent in that iteration)
Iteration	Permanent set S	A	B	C	D	E	G
0 (init)	—	∞	∞	∞	∞	∞	∞
1	F	∞	∞	2 (F)	1 (F)	1 (F)	3 (F)
2	F, D	3 (D)	∞	2 (F)	1	1 (F)	3 (F)
3	F, D, E	3 (D)	6 (E)	2 (F)	1	1	2 (E)
4	F, D, E, C	3 (D)	6 (E)	2	1	1	2 (E)
5	F, D, E, C, G	3 (D)	6 (E)	2	1	1	2
6	F, D, E, C, G, A	3	4 (A)	2	1	1	2
7	all	3	4	2	1	1	2

Check: the edge list is read from the printed drawing of the paper; the ten distances and the vertical C–D and E–F rungs are as printed there. The tie at node C is genuine — F–C and F–D–C both cost 2 — so an answer book quoting either path for C is correct, and the tie between D and E at distance 1 means the permanent order may equally be F, E, D, C, G, A, B with identical final labels.

Question 5 — shortest paths from node F
Destination	Shortest distance	Path	Made permanent in iteration
D	1	F–D	2
E	1	F–E	3
C	2	F–C (ties with F–D–C)	4
G	2	F–E–G	5
A	3	F–D–A	6
B	4	F–D–A–B	7
Total cost of the shortest-path tree	13

Topic. Link-state routing: Dijkstra's shortest-path-first algorithm, the shortest-path tree it produces, and why the greedy single pass is correct.

Key relations. Relaxation $d(v)\leftarrow\min\!\left(d(v),\,d(u)+w(u,v)\right)$ for every edge out of the newly permanent node u; termination when every node is permanent. Complexity $O(|E|\log|V|)$ with a binary heap, or $O(|V|^{2})$ with the linear scan used by hand. The forwarding table at the source is read from the first hop of each path, so F's table sends traffic for A, B and D out of the F–D interface, traffic for E and G out of F–E, and traffic for C out of F–C.

Why this works. The correctness rests on non-negative edge weights. When the algorithm removes the unvisited node u of least tentative distance, any other route to u would have to leave the permanent set through some unvisited node x, and $d(x)\ge d(u)$ by the choice of u; since the remaining edges from x to u cannot reduce that, no such route can be shorter. The label is therefore final on removal and never needs revisiting, which is what buys the single pass. This is also precisely why the algorithm fails on negative weights — the assumption that going further cannot get cheaper is what breaks — and why link-state protocols such as OSPF and IS-IS, which run this algorithm on a flooded copy of the whole topology database, define link costs as positive metrics.

Common pitfall. Relaxing from the node most recently relaxed instead of the unvisited node with the smallest label, which quietly turns the run into a breadth-first search and gets G wrong here (it would keep the direct F–G edge at 3 instead of finding F–E–G at 2). The second pitfall is stopping when the destination is first assigned a finite label rather than when it is made permanent — node B is labelled 6 in iteration 3 and only settles at 4 in iteration 6. The third is failing to record predecessors, which leaves the distances correct but the question's actual demand, the paths, unanswered.

Source. Leon-Garcia and Widjaja, Communication Networks, 2nd ed., §7.5 (shortest-path routing, Dijkstra and Bellman-Ford); Kurose and Ross, Computer Networking, 8th ed., §5.2; Tanenbaum and Wetherall, Computer Networks, 5th ed., §5.2.2.

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

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