In a transport network, all the nodes (represented by A, B, C, D, E, F, G, H) and their connecting links are shown in the figure below. The values mentioned alongside the links represent the travel time (in minutes) between nodes. Following the shortest path, the minimum time required to commute from node A to node G (in minutes) is (in integer).
Show Hint
Apply Dijkstra's shortest path method starting from node A, updating the running minimum time to each node until G is settled.
Step 1: List the edges and their weights from the figure.
Reading the given network, the connections (travel times in minutes) are:
A-B = 10, A-C = 8, B-C = 8, B-D = 5, B-H = 20, C-D = 9, C-E = 10, D-E = 5, D-F = 6, D-H = 7, E-F = 7, E-G = 15, F-G = 8, F-H = 5, H-G = 12.
We need the shortest (least total time) path from A to G.
Step 2: Apply Dijkstra's method, settling the nearest unvisited node at each pass.
Start with \(A = 0\) and every other node at infinity.
From A, reach B at \(10\) and C at \(8\). The smallest is C, so settle \(C = 8\).
Step 3: Expand from C.
From C: to B, \(8+8=16\), worse than the current \(10\), so B stays \(10\). To D, \(8+9=17\). To E, \(8+10=18\).
The smallest unsettled value now is B, so settle \(B = 10\).
Step 4: Expand from B.
From B: to D, \(10+5=15\), better than \(17\), so update \(D = 15\). To H, \(10+20=30\).
The smallest unsettled value now is D, so settle \(D = 15\).
Step 5: Expand from D.
From D: to H, \(15+7=22\), better than \(30\), update \(H=22\). To F, \(15+6=21\). To E, \(15+5=20\), which is worse than the current \(18\), so E stays \(18\).
The smallest unsettled value now is E, so settle \(E = 18\).
Step 6: Expand from E, then F.
From E: to F, \(18+7=25\), worse than the current \(21\), so F stays \(21\). To G, \(18+15=33\).
The smallest unsettled value now is F, so settle \(F = 21\). From F: to H, \(21+5=26\), worse than \(22\), no change. To G, \(21+8=29\), better than \(33\), update \(G=29\).
Step 7: Expand from H, then confirm G.
Settle \(H = 22\) (nothing smaller is left to challenge it). From H: to G, \(22+12=34\), worse than the current \(29\), so G stays at \(29\). No unsettled node can now improve G, so \(G = 29\) is final.
Final Answer:
The shortest route is A -> B -> D -> F -> G, with total time \(10+5+6+8=29\) minutes.
\[ \boxed{29 \text{ minutes}} \]
