| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with unknown edge weight |
| Difficulty | Challenging +1.2 This question requires applying Dijkstra's algorithm with an algebraic parameter and analyzing how the shortest path changes as y varies, then repeating for max flow. While it involves multiple parts and two different algorithms, the techniques are standard D1 content with straightforward case analysis. The conceptual demand is moderate—students must recognize critical values where paths change—but the execution is methodical rather than requiring novel insight. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04f Network problems: choosing appropriate algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| (a) If \(y = 0\), lowest weight = 22 (SADT). If \(y\) large, lowest weight = 27 (SBDT). \(\therefore\) lowest weight between 22 and 27 inclusive | M2 A1 | |
| (b) If \(y = 0\), minimum cut = 14, \(\{S, A, B, C, E\} | \{D, T\}\). If \(y\) large, minimum cut = 22, \(\{S, A, B, C, D, E\} | \{T\}\). Maximum flow = minimum cut \(\therefore\) between 14 and 22 inclusive |
| (c) (i) e.g. shortest route by road between 2 towns | B1 | |
| (ii) e.g. maximum traffic flow between 2 towns | B1 | (8) |
**(a)** If $y = 0$, lowest weight = 22 (SADT). If $y$ large, lowest weight = 27 (SBDT). $\therefore$ lowest weight between 22 and 27 inclusive | M2 A1 |
**(b)** If $y = 0$, minimum cut = 14, $\{S, A, B, C, E\} | \{D, T\}$. If $y$ large, minimum cut = 22, $\{S, A, B, C, D, E\} | \{T\}$. Maximum flow = minimum cut $\therefore$ between 14 and 22 inclusive | M2 A1 |
**(c)** (i) e.g. shortest route by road between 2 towns | B1 |
| (ii) e.g. maximum traffic flow between 2 towns | B1 | (8) |
---3.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{63f3ba38-8bca-4684-957f-aca7104f2f3e-03_734_1353_196_317}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
Figure 1 shows a graph in which $y \geq 0$.\\
Given that the graph is a weighted network,
\begin{enumerate}[label=(\alph*)]
\item find the range of values for the path of lowest weight from $S$ to $T$.
Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
\item find the range of values for the maximum flow from $S$ to $T$.
\item Give an example of a practical problem which could be solved by using:
\begin{enumerate}[label=(\roman*)]
\item the weighted network in part (a),
\item the capacitated network in part (b).
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q3 [8]}}