Question 4 of 5: Shortest-Path Routing — Bellman-Ford from Node H

Question 4: Shortest-Path Routing — Bellman-Ford from Node H (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 above, read from the printed figure:

Eleven edges over eight nodes; all costs positive. Source node: H.

Find. The least-cost path from H to every other node, obtained by the Bellman-Ford algorithm, with the work shown iteration by iteration.

Approach. Initialise the distance estimate of the source to zero and of every other node to infinity, then repeatedly sweep the whole edge list applying the relaxation test $d(v) \leftarrow \min\{d(v),\,d(u) + w(u,v)\}$ in both directions of each undirected edge, until a complete sweep changes nothing. With $|V| = 8$ nodes, at most $|V| - 1 = 7$ sweeps can be needed.

1. State the algorithm being applied. Bellman-Ford maintains a distance estimate $d(v)$ and a predecessor $p(v)$ for every node. It does not maintain a set of “settled” nodes, and it does not choose the cheapest unvisited node next — that is Dijkstra. Every iteration relaxes every edge: $$\text{if } d(u) + w(u,v) < d(v) \;\text{ then }\; d(v) \leftarrow d(u) + w(u,v), \quad p(v) \leftarrow u .$$ Because the graph is undirected, each listed edge is relaxed in both directions. After $k$ complete iterations, $d(v)$ is guaranteed correct for every node whose shortest path from H uses at most $k$ edges — that is the invariant the marks are for.
2. Initialise. $d(\mathrm{H}) = 0$ and $d(v) = \infty$ for all other $v$; every predecessor is undefined. Fix an edge-relaxation order for the sweeps — alphabetical by edge, as listed in the Given table — so that the work is reproducible.
3. Iteration 1 (paths of at most one edge). Only edges incident on H can relax, because every other node still has $d = \infty$. Edge F–H gives $d(\mathrm{F}) = 0 + 1 = 1$ with $p(\mathrm{F}) = \mathrm{H}$; edge G–H gives $d(\mathrm{G}) = 0 + 3 = 3$ with $p(\mathrm{G}) = \mathrm{H}$. Within the same sweep, later edges may already exploit these: D–F gives $d(\mathrm{D}) = 1 + 2 = 3$ and E–F gives $d(\mathrm{E}) = 1 + 1 = 2$, and then B–E gives $d(\mathrm{B}) = 3$ and C–E gives $d(\mathrm{C}) = 4$. The table below records the estimate at the end of each sweep.
4. Iteration 2 and the sweeps that follow. The second sweep relaxes A–B, giving $d(\mathrm{A}) = d(\mathrm{B}) + 1 = 4$ with $p(\mathrm{A}) = \mathrm{B}$; it also tests A–C, which offers $d(\mathrm{C}) + 5 = 9$ and is rejected as worse. Every other test in the sweep fails to improve anything: F–G offers $d(\mathrm{F}) + 2 = 3$, which merely ties the existing $d(\mathrm{G}) = 3$; E–G offers $2 + 2 = 4$, worse; B–D offers $3 + 2 = 5$ against the established 3. The third sweep changes nothing, which is the algorithm's termination condition.
5. The relaxation table. Distance estimates at the end of each sweep (a dash is $\infty$):

   Iteration	A	B	C	D	E	F	G	H
   0 (init)	—	—	—	—	—	—	—	0
   1	—	3	4	3	2	1	3	0
   2	4	3	4	3	2	1	3	0
   3 (no change)	4	3	4	3	2	1	3	0

   Two sweeps suffice here, well inside the guaranteed bound of seven, because no shortest path from H uses more than four edges. A third sweep is still required to prove convergence — and, in the general case, a further sweep that still improved something would reveal a negative-cost cycle. All weights here are positive, so none exists.
6. Read the paths back through the predecessors. Following $p(\cdot)$ from each node back to H, and re-adding the edge costs independently as a check: $$\boxed{\begin{aligned} d(\mathrm{F}) &= 1 &&: \mathrm{H}\!-\!\mathrm{F} \\ d(\mathrm{E}) &= 2 &&: \mathrm{H}\!-\!\mathrm{F}\!-\!\mathrm{E} \\ d(\mathrm{B}) &= 3 &&: \mathrm{H}\!-\!\mathrm{F}\!-\!\mathrm{E}\!-\!\mathrm{B} \\ d(\mathrm{D}) &= 3 &&: \mathrm{H}\!-\!\mathrm{F}\!-\!\mathrm{D} \\ d(\mathrm{G}) &= 3 &&: \mathrm{H}\!-\!\mathrm{G} \\ d(\mathrm{C}) &= 4 &&: \mathrm{H}\!-\!\mathrm{F}\!-\!\mathrm{E}\!-\!\mathrm{C} \\ d(\mathrm{A}) &= 4 &&: \mathrm{H}\!-\!\mathrm{F}\!-\!\mathrm{E}\!-\!\mathrm{B}\!-\!\mathrm{A} \end{aligned}}$$
7. Check the result and note the ties. Node G is a genuine tie: the direct edge H–G costs 3 and the route H–F–G also costs $1 + 2 = 3$, so which one appears depends only on the order in which the edges were relaxed — both are correct answers and either should be stated. Node D is reached through F for 3, not through B for $3 + 2 = 5$. Node A is reached through B for 4 rather than by the direct A–C–E route, which costs $4 + 5 = 9$. The seven tree edges sum to $1 + 3 + 1 + 2 + 1 + 2 + 1 = 11$, and every node is attached exactly once, confirming a spanning tree on eight nodes.

Final results.

Total weight of the shortest-path tree: 11. Sweeps required: 2 to converge, 3 to prove convergence.