| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Session | Specimen |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Chinese Postman with start/end constraints |
| Difficulty | Standard +0.3 This is a standard Chinese Postman problem with straightforward application of Dijkstra's algorithm and identifying odd-degree vertices. Part (d) requires basic reasoning about how adding an edge affects the route length, but all parts follow textbook procedures with no novel insight required. Slightly easier than average due to clear algorithmic steps. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| For 213 or 189 + their shortest repeat | B1ft | Follow through on their values |
| For translating the information in the question into an equation involving \(x\), \(2x\) and 34 | M1 | |
| A correct equation leading to \(BG = 10\) (m) | A1 |
## Question 1(c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| For 213 or 189 + their shortest repeat | B1ft | Follow through on their values |
| For translating the information in the question into an equation involving $x$, $2x$ and 34 | M1 | |
| A correct equation leading to $BG = 10$ (m) | A1 | |
---1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{1e2c1dc4-3724-4bba-961c-1c2ae7e649c4-2_698_1173_447_443}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
[The total weight of the network is 189]\\
Figure 1 represents a network of pipes in a building. The number on each arc is the length, in metres, of the corresponding pipe.
\begin{enumerate}[label=(\alph*)]
\item Use Dijkstra's algorithm to find the shortest path from A to F . State the path and its length.
On a particular day, Gabriel needs to check each pipe. A route of minimum length, which traverses each pipe at least once and which starts and finishes at A, needs to be found.
\item Use an appropriate algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
\item State the minimum length of Gabriel's route.
A new pipe, BG, is added to the network. A route of minimum length that traverses each pipe, including BG, needs to be found. The route must start and finish at A.
Gabriel works out that the addition of the new pipe increases the length of the route by twice the length of BG .
\item Calculate the length of BG. You must show your working.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS Q1 [12]}}