22-Elec-B4 Information Technology Networks · May 2018

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

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. Professional Engineers of Ontario — National Examinations, May 2018, 16-Elec-B4 Information Technology Networks. Three hours, closed book; one Casio or Sharp approved calculator permitted. The paper prints five questions of 25 marks each and any four constitute a complete paper worth 100 marks, with the marks for every sub-part shown in the left margin. All five questions are solved here, because this set is a study resource rather than an exam attempt, and because a candidate choosing which four to answer benefits from seeing the fifth worked out.

Reference texts. A. Leon-Garcia and I. Widjaja, Communication Networks: Fundamental Concepts and Key Architectures, 2nd ed. (the syllabus reference for this code); J. F. Kurose and K. W. Ross, Computer Networking: A Top-Down Approach, 8th ed.; A. S. Tanenbaum and D. J. Wetherall, Computer Networks, 5th ed.; W. Stallings, Wireless Communications and Networks, 2nd ed.; T. S. Rappaport, Wireless Communications: Principles and Practice, 2nd ed.; S. Sesia, I. Toufik and M. Baker, LTE — The UMTS Long Term Evolution, 2nd ed.

Source reading — Question 3 figure. The printed network labels two different nodes with the letter F: one on the upper row between D and the right-hand vertex, and one at the far right. This is a typographical slip in the examination paper. To keep the working unambiguous the far-right node is written F′ throughout; every distance and path below is unaffected by the naming, and a candidate should simply state the convention adopted, exactly as the paper's own instruction on assumptions invites.

Source reading — Question 2(d). The printed text says “Repeat part b”, but part (b) is the qualitative question about congestion in wired networks and carries no window to repeat. The intended reference is part (c), whose window evolution is the thing a lost packet perturbs. Part (d) is answered on that reading, and the reading is stated in the answer rather than assumed silently.

Question 3: Shortest-Path Routing — 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, positively weighted network of eight nodes, with the eleven edges read from the printed figure:

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

Find. The shortest distance and the corresponding path from node A to every other node, obtained by a correct execution of Dijkstra's algorithm with the working shown at each iteration.

[Figure not reproduced: Figure 3.1 — The network as printed on page 3 of the examination paper, with the edge distances marked. The paper labels two distinct nodes F; the far-right one is written F′ here. See the official exam paper.]

Approach. Maintain a set $S$ of nodes whose shortest distance from A is final, and a tentative label $D(v)$ for every node outside it. Initialise $S=\{\text{A}\}$ with $D(v)$ equal to the direct edge from A where one exists and infinity otherwise; then repeatedly move the unlabelled node of smallest tentative distance into $S$ and relax its edges. Eight nodes require seven iterations.

Initialise. Set $D(\text{A})=0$ and, for every other node, the direct distance from A: $$S=\{\text{A}\},\qquad D(\text{B})=1,\quad D(\text{C})=5,\quad D(\text{D})=D(\text{E})=D(\text{F})=D(\text{G})=D(\text{F}')=\infty$$ The predecessor of B and of C is A; the others have none yet.
Iteration 1 — add B ($D=1$), the smallest tentative label. Relax B's edges, replacing $D(v)$ by $D(\text{B})+w(\text{B},v)$ wherever that is smaller: $$D(\text{D}) = 1+2 = 3\ (\text{via B}),\qquad D(\text{E}) = 1+1 = 2\ (\text{via B})$$ Now $S=\{\text{A},\text{B}\}$ and the labels are D(C)=5, D(D)=3, D(E)=2, the rest infinite.
Iteration 2 — add E ($D=2$). E is the smallest remaining label. Relaxing its three edges: $$D(\text{C}) = \min(5,\ 2+2) = 4\ (\text{via E}),\quad D(\text{F}) = 2+1 = 3\ (\text{via E}),\quad D(\text{G}) = 2+2 = 4\ (\text{via E})$$ Notice the first of these: the four-hop route A–B–E–C beats the direct edge A–C of length 5. This is the substance of the question — a direct link is not a short one.
Iteration 3 — add D ($D=3$). D and F are tied at 3; taking D first (either order gives the same final answer, and it is worth saying so): $$D(\text{F}) = \min(3,\ 3+2) = 3\ \ \text{unchanged}$$
Iteration 4 — add F ($D=3$). Relaxing F's remaining edges: $$D(\text{G}) = \min(4,\ 3+2) = 4\ \ \text{unchanged},\qquad D(\text{F}') = 3+1 = 4\ (\text{via F})$$
Iterations 5–7 — add C, G and F′ (all at $D=4$). The three remaining nodes are tied at 4 and none of them improves any other: $$D(\text{F}') = \min(4,\ D(\text{G})+3) = \min(4,\ 7) = 4$$ All eight nodes are now in $S$ and the algorithm terminates.
Read off the shortest-path tree. Tracing each node's predecessor back to A gives the final distance vector $$\boxed{\,D(\text{B})=1,\quad D(\text{E})=2,\quad D(\text{D})=D(\text{F})=3,\quad D(\text{C})=D(\text{G})=D(\text{F}')=4\,}$$ with the corresponding paths A–B, A–B–E, A–B–D, A–B–E–F, A–B–E–C, A–B–E–G and A–B–E–F–F′ respectively; they are collected node by node in the results table below.

The iteration table below is the form in which the working is normally presented, and it is what a marker looks for: one row per iteration, the node added, and the tentative labels after that node's edges have been relaxed. An entry in bold is final.

Dijkstra iteration table — tentative distances from A after each node is added
Iter.	Added	B	C	D	E	F	G	F′
0	A (0)	1	5	∞	∞	∞	∞	∞
1	B (1)	1	5	3	2	∞	∞	∞
2	E (2)	1	4	3	2	3	4	∞
3	D (3)	1	4	3	2	3	4	∞
4	F (3)	1	4	3	2	3	4	4
5	C (4)	1	4	3	2	3	4	4
6	G (4)	1	4	3	2	3	4	4
7	F′ (4)	1	4	3	2	3	4	4

Figure 3.2 — The shortest-path tree rooted at A, drawn heavy over the original network. Seven tree edges span the eight nodes; the direct edge A–C (5) and the edges F–G and G–F′ are not used by any shortest path.

Three checks confirm the result, and each is worth a line in an examination answer. The tree has seven edges for eight nodes, as any spanning tree must. Every node's distance equals its parent's distance plus the connecting edge weight, so the labels are internally consistent. And each unused edge fails the improvement test: the direct A–C edge of 5 loses to 4, reaching G by way of F costs $3+2=5$ against 4 by way of E, and reaching F′ by way of G costs $4+3=7$ against 4 by way of F.

Final results — Question 3: shortest paths from A
Destination	Shortest distance	Shortest path
B	1	A–B
E	2	A–B–E
D	3	A–B–D
F	3	A–B–E–F
C	4	A–B–E–C (not the direct edge of length 5)
G	4	A–B–E–G
F′	4	A–B–E–F–F′

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

Key relations. The relaxation step, $D(v) \leftarrow \min\{D(v),\ D(u)+w(u,v)\}$ applied to every neighbour $v$ of the node $u$ just made permanent; termination after $|V|-1$ iterations; complexity $O(|V|^2)$ with a linear scan for the minimum, or $O(|E|\log|V|)$ with a binary heap. Bellman's optimality principle — every sub-path of a shortest path is itself a shortest path — is what licenses the greedy choice.

Why this works. The invariant is that when a node is moved into the permanent set, its label is already its true shortest distance. Suppose not: then some shorter path to it must leave the permanent set at some point, and the first node of that path outside the set would carry a tentative label smaller than the one just selected — contradicting the fact that the smallest tentative label was chosen. The argument needs all weights to be non-negative, which is why Dijkstra fails on graphs with negative edges and Bellman–Ford is used instead. This is the algorithm behind OSPF and IS-IS: every router floods its link states, each builds the identical topological map, and each runs this computation with itself as the root, so the resulting forwarding tables are consistent and loop-free by construction — the property distance-vector protocols such as RIP have to work hard to achieve.

Common pitfall. The instruction “credit will not be awarded unless Dijkstra's algorithm is correctly followed” means the iteration table is the answer, not the distances. Marks are lost by reading shortest paths off the picture by inspection; by relaxing the edges of a node before it has been made permanent; by forgetting to record predecessors, so that the distances are right but the paths cannot be stated; and by stopping when the nominal destination is reached when the question asks for all nodes. On this particular network the trap is node C, where the tempting direct edge of length 5 is not the shortest path.

Source. Leon-Garcia & Widjaja, Communication Networks, 2nd ed., §7.5 (shortest-path routing algorithms); Kurose & Ross, Computer Networking, 8th ed., §5.2 (link-state routing); Tanenbaum & Wetherall, Computer Networks, 5th ed., §5.2.2.

← Question 2 Next: Question 4 →