Question 6 of 8: Design an Algorithm — Jerry's Cheapest Flight

Question 6: Design an Algorithm — Jerry's Cheapest Flight (20 marks: 5,3,3,5,2,2)

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.

1. Graph representation — 5 marks

Model the situation as a directed, weighted graph $G=(V,E)$. Each vertex is a city (Yellowknife and Kingston included); each edge $(u,v)$ is a direct flight from city $u$ to city $v$, labelled with its cost (taxes included). Because "there may be more than one flight between any two cities," this is formally a multigraph — parallel edges between the same pair of cities are allowed and each is kept as a separate edge with its own cost, rather than collapsed to one. Since every flight only goes from a nearer city to a farther one, the "nearest → farthest" ordering supplied in the input is already a valid topological order of $G$ — equivalently, $G$ is guaranteed to be a directed acyclic graph (DAG).

2. Property of a solution — 3 marks

A solution is a directed path $P = (\text{Yellowknife} = v_0, v_1, \dots, v_k = \text{Kingston})$ in $G$, where each consecutive pair $(v_{i-1}, v_i)$ is a real edge (an actual flight). Its cost is the sum of the edge weights along it, $\text{cost}(P) = \sum_{i=1}^{k} w(v_{i-1}, v_i)$; the problem asks for the path of minimum total cost among all such Yellowknife-to-Kingston paths — the classic single-source, single-target shortest-path property.

3. Data structure — 5 marks

An adjacency list indexed by the given nearest-to-farthest city order is the natural fit: each city stores only its outgoing flights (edges only ever point "forward" in this order), so no wasted space is spent on directions that can never occur.

#define MAX_CITIES 1000

typedef struct Edge {
    int to;                 /* destination city index (always > 'from' city's index) */
    int cost;
    struct Edge* next;      /* next parallel/other outgoing flight from this city */
} Edge;

Edge* adj[MAX_CITIES];      /* adj[u] = linked list of u's outgoing flights */
int   cityIndex[MAX_CITIES];/* 0 = Yellowknife ... N-1 = Kingston, in given order */

4. Algorithm — 5 marks

Approach. Because $G$ is a DAG and a topological order (the given nearest-to-farthest list) is already known for free, the shortest path can be found with a single linear scan using dynamic programming — no priority queue is needed at all.

1. Initialize. $\text{dist}[\text{Yellowknife}] = 0$, $\text{dist}[v] = \infty$ for every other city, $\text{pred}[v] = \text{undefined}$.
2. Relax in topological order. Process cities $v_0, v_1, \dots, v_{N-1}$ in the given nearest-to-farthest order. For each city $u$ just processed, scan its outgoing edges $(u,v,\text{cost})$ and relax: if $\text{dist}[u] + \text{cost} < \text{dist}[v]$, set $\text{dist}[v] = \text{dist}[u]+\text{cost}$ and $\text{pred}[v] = u$.
3. Read off the answer. $\text{dist}[\text{Kingston}]$ is the minimum cost; the actual flight sequence is recovered by following $\text{pred}$ pointers backward from Kingston to Yellowknife and reversing the list.

This is exactly Dijkstra's algorithm specialised to a DAG: because the input order already guarantees that once a city is processed no cheaper path to it can ever appear later (every edge only moves forward in that order), a node never needs to be "revisited," so the usual min-priority-queue machinery of general Dijkstra is unnecessary. (Dijkstra's algorithm with a binary heap is an equally correct, if slightly heavier, alternative — it does not need the DAG property and would still find the optimum since all costs are non-negative.)

5. Complexity — 2 marks

Every city is processed once and every edge is relaxed exactly once, so the DAG-DP algorithm runs in $\boxed{O(V+E)}$ time and $O(V+E)$ space (for the adjacency list plus $\text{dist}$/$\text{pred}$ arrays) — linear in the size of the flight network. (General Dijkstra with a binary heap, if used instead, costs $O((V+E)\log V)$.)

6. Limiting the number of stopovers to n — 2 marks

A hop limit turns this into a resource-constrained shortest path problem, and a single scalar $\text{dist}[v]$ is no longer enough — the cheapest path to $v$ using at most $k$ edges can differ from the cheapest path using at most $k+1$ edges. The fix is to add a second dimension to the state: let $\text{dist}[v][k]$ = minimum cost to reach $v$ using at most $k$ flights. Process $k = 0, 1, \dots, n$ in order (an extra outer loop around the same topological relaxation), where $\text{dist}[v][k]$ relaxes from $\text{dist}[u][k-1]$ across every edge $(u,v)$. The final answer is $\min_{k \le n} \text{dist}[\text{Kingston}][k]$. This costs $O(n\cdot(V+E))$ time and $O(n\cdot V)$ space — still polynomial because the graph is a DAG with a known topological order, though $n$ times more expensive than the unconstrained version.