Question 2 of 8: Dynamic Programming — Shortest Path Through a Street Grid
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2017 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 160 marks across 8 questions (each worth 20) and only 100 marks are required, so a candidate would normally answer 5 — all eight are solved below for completeness.
Given. A $5\times4$ street grid (5 vertical streets × 4 horizontal streets) with the block travel times (minutes) shown in the figure below; start = King & Bathurst, destination = College & Yonge; the rat moves only rightward (increasing street number) or upward (toward College), never backtracking, consistent with heading toward the destination.
Find. The minimum total travel time from King & Bathurst to College & Yonge, and the shortest route.
Street grid, node label = street + row (row 0 = King, 1 = Queen, 2 = Dundas, 3 = College; columns left→right = Bathurst, Spadina, University, Bay, Yonge). Numbers on each block are the travel time in minutes. Start = Bath0 (King&Bathurst); destination = Yong3 (College&Yonge).
Approach. Index intersections by (column, row); define $f(x,y)$ as the minimum time from the start to intersection $(x,y)$, and apply the DP recursion $f(x,y)=\min\{f(x{-}1,y)+h(x{-}1,y),\ f(x,y{-}1)+v(x,y{-}1)\}$ sweeping outward from the start, since only rightward/upward moves can reach the destination without wasted travel.
Stage-by-stage DP fill (minutes to reach each intersection). Rows are King(0), Queen(1), Dundas(2), College(3); columns are Bathurst(0), Spadina(1), University(2), Bay(3), Yonge(4). Boundary $f(0,0)=0$.
DP table — minimum minutes from Bath0 to each intersection
Bathurst
Spadina
University
Bay
Yonge
College
7
12
13
14
18
Dundas
5
9
11
13
15
Queen
3
7
9
12
13
King
0
5
7
9
12
Each cell is the smaller of (cell to its left + that horizontal block time) and (cell below it + that vertical block time); e.g. $f(\text{Spadina},\text{Queen})=\min\big(f(\text{Bathurst},\text{Queen})+8,\ f(\text{Spadina},\text{King})+2\big)=\min(3+8,\ 5+2)=7$, matching the table.
Trace the optimal path backward from the destination by following whichever predecessor achieved the minimum at each step:
$$\boxed{f(\text{Yonge},\text{College})=18\text{ minutes}}$$
Path: Bathurst&King $\xrightarrow{5}$ Spadina&King $\xrightarrow{2}$ Spadina&Queen $\xrightarrow{2}$ Spadina&Dundas $\xrightarrow{2}$ University&Dundas $\xrightarrow{2}$ University&College $\xrightarrow{1}$ Bay&College $\xrightarrow{4}$ Yonge&College. Check: $5+2+2+2+2+1+4=18$, matching the DP table value, and this is exactly the chain of predecessors the recursion selected at each stage.
