| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Dijkstra with vertex or edge exclusion |
| Difficulty | Moderate -0.3 Part (a) is a standard Dijkstra's algorithm application, which is routine for D1 students. Part (b) requires re-examining the solution to exclude vertex C, but this is straightforward once part (a) is complete—typically just identifying an alternative path from the working. The question is slightly easier than average because Dijkstra is a well-practiced algorithmic procedure with minimal problem-solving required. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Dijkstra's algorithm applied correctly with small replacing larger working values at C, E, G or H | M1 | Small replacing larger in at least one of the sets of working values at C, E, G or H |
| Values correct at vertices A to E | A1 | |
| Values correct at vertices F to H | A1ft | Penalise order only once |
| cao (final answer correct) | A1 | |
| Shortest route: A B C E G H, Length: 156 (km) | A1ft | 156ft |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| New route: A B E G H | B1 | cao ABEGH |
| Length: 165 (km) | B1 | Special case: accept 166 if ABDGH listed as path |
# Question 6:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Dijkstra's algorithm applied correctly with small replacing larger working values at C, E, G or H | M1 | Small replacing larger in at least one of the sets of working values at C, E, G or H |
| Values correct at vertices A to E | A1 | |
| Values correct at vertices F to H | A1ft | Penalise order only once |
| cao (final answer correct) | A1 | |
| Shortest route: A B C E G H, Length: 156 (km) | A1ft | 156ft |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| New route: A B E G H | B1 | cao ABEGH |
| Length: 165 (km) | B1 | Special case: accept 166 if ABDGH listed as path |
---6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ef029462-ffed-4cdf-87bc-56c8a13d671f-6_609_1283_260_392}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
Figure 4 shows a network of roads through eight villages, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }$ and H . The number on each arc is the length of that road in km .
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest route from A to H. State your shortest route and its length.\\
(5)
There is a fair in village C and you cannot drive through the village. A shortest route from A to H which avoids C needs to be found.
\item State this new minimal route and its length.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q6 [7]}}