| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with route via intermediate vertex |
| Difficulty | Easy -1.3 This is a straightforward application of Dijkstra's algorithm, a standard D1 topic. Part (a) tests basic definition recall, part (b) is a routine algorithmic procedure with structured working boxes provided, part (c) asks for explanation of a standard process, and part (d) requires minimal adaptation (combining two shortest paths). No problem-solving insight or novel thinking required—purely procedural execution of a well-practiced algorithm. |
| Spec | 7.02c Graph terminology: walk, trail, path, cycle, route7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks |
|---|---|
| (a) A path is a finite sequence of edges, such that the end vertex of one edge is the start vertex of the next and is which no vertex appears more than once [no cycle] | B2,1,0(2) |
| (b) [Network diagram with shortest path: ABDFGI, length 108 miles] | A1 A1(c) |
| (c) e.g. 108 - 21 = 87 ✓✓ -traceback from I; 87 - 15 = 72 FG; 72 - 21 = 51 DF; 51 - 28 = 23 BD; 23 - 23 = 0 AB | B2/1(D)(2) |
| (d) ABEDPGI length 118 miles | m1 A1(2) |
| (e) B2: A good, complete description. B1: close - mostly there...just set B), 'and',...may be ch. A: B, C, E correct labels in a rising sequence. A1: D, F correct labels. A1(G H I correct label. Path CAO. A1(: length ✓ from I in great 108 ✓ a correct path | m1 A1(2) |
(a) A path is a finite sequence of edges, such that the end vertex of one edge is the start vertex of the next and is which no vertex appears more than once [no cycle] | B2,1,0(2)
(b) [Network diagram with shortest path: ABDFGI, length 108 miles] | A1 A1(c)
(c) e.g. 108 - 21 = 87 ✓✓ -traceback from I; 87 - 15 = 72 FG; 72 - 21 = 51 DF; 51 - 28 = 23 BD; 23 - 23 = 0 AB | B2/1(D)(2)
(d) ABEDPGI length 118 miles | m1 A1(2)
(e) B2: A good, complete description. B1: close - mostly there...just set B), 'and',...may be ch. A: B, C, E correct labels in a rising sequence. A1: D, F correct labels. A1(G H I correct label. Path CAO. A1(: length ✓ from I in great 108 ✓ a correct path | m1 A1(2)
(m1) Route A b I including E. A1 cao
---\begin{enumerate}[label=(\alph*)]
\item Explain what is meant by the term 'path'. [2]
\end{enumerate}
\includegraphics{figure_3}
Figure 3 shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Mary wishes to cycle from A to I as part of a cycling holiday. She wishes to minimise the distance she travels.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Use Dijkstra's algorithm to find the shortest path from A to I. Show all necessary working in the boxes in Diagram 1 in the answer book. State your shortest path and its length. [6]
\item Explain how you determined the shortest path from your labelling. [2]
\end{enumerate}
Mary wants to visit a theme park at E.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{3}
\item Find a path of minimal length that goes from A to I via E and state its length. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2006 Q4 [12]}}