| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with vertex or edge exclusion |
| Difficulty | Moderate -0.3 This is a straightforward application of Dijkstra's algorithm with standard follow-up questions. Part (a) is definitional recall, parts (b) and (c) are routine algorithm application, and part (d) simply requires re-running the algorithm with one edge removed—a common textbook exercise requiring no novel insight or complex problem-solving. |
| Spec | 7.02c Graph terminology: walk, trail, path, cycle, route7.04a Shortest path: Dijkstra's algorithm |
4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-4_629_1392_187_319}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Explain what is meant, in a network, by the term path.\\
(2)
Figure 4 represents a network of canals. The number on each arc represents the length, in miles, of the corresponding canal.
\item Use Dijkstra's algorithm to find the shortest path from S to T . State your path and its length.
\item Write down the length of the shortest path from S to F .
Next week the canal represented by $\operatorname { arc } \mathrm { AB }$ will be closed for dredging.
\item Find a shortest path from S to T avoiding AB and state its length.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2013 Q4 [11]}}