Question

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).

Hint:

Apply Dijkstra's shortest path method starting from node A, updating the running minimum time to each node until G is settled.

Answer 1

Correct Answer: 29

Step 1: Shortlist the routes that look short by inspection.
Instead of a formal labeling algorithm, list out the routes from A to G that avoid obviously long detours (like the $20$-minute A-B-H edge) and add up their distances directly.

Step 2: Route through C and E.
$A - C - E - G$: $8 + 10 + 15 = 33$ minutes.

Step 3: Route through B, D and H.
$A - B - D - H - G$: $10 + 5 + 7 + 12 = 34$ minutes.

Step 4: Route through C and D.
$A - C - D - F - G$: $8 + 9 + 6 + 8 = 31$ minutes.

Step 5: Route through B, D and F.
$A - B - D - F - G$: $10 + 5 + 6 + 8 = 29$ minutes.
This beats every other route checked so far.

Step 6: Check that no shorter combination is possible.
Any route reaching $G$ must pass through either $F$ ($8$ min from $G$) or $H$ ($12$ min from $G$) or $E$ ($15$ min from $G$), since these are the only three nodes directly linked to $G$. Getting to $F$ takes at least $10+5+6=21$ minutes (via $B-D-F$), so the cheapest approach to $G$ through $F$ is $21+8=29$. Getting to $H$ or $E$ costs at least $22$ or $18$ minutes respectively before adding their (larger) links to $G$, both of which give totals above $29$.

Step 7: Conclude.
The minimum time to commute from $A$ to $G$ is 29 minutes, along $A - B - D - F - G$.
\[ \boxed{29 \text{ minutes}} \]