| Exam Board | Edexcel |
|---|---|
| Module | FD1 (Further Decision 1) |
| Year | 2021 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Critical Path Analysis |
| Type | Draw activity network from table |
| Difficulty | Standard +0.3 This is a standard Floyd's algorithm question with routine Chinese Postman extension. Parts (a)-(b) involve mechanical application of Floyd's algorithm steps, while parts (c)-(d) require identifying odd vertices and applying the Chinese Postman algorithm—all textbook procedures for FP1/FD1 with no novel problem-solving required. Slightly easier than average due to the algorithmic, procedural nature. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04f Network problems: choosing appropriate algorithm |
| \cline { 2 - 7 } \multicolumn{1}{c|}{} | A | B | C | D | E | F |
| A | - | 57 | 95 | 147 | 63 | 220 |
| B | 57 | - | 72 | 204 | 120 | 197 |
| C | 95 | 72 | - | 242 | 158 | 125 |
| D | 147 | 204 | 242 | - | 84 | 275 |
| E | 63 | 120 | 158 | 84 | - | 191 |
| F | 220 | 197 | 125 | 275 | 191 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Initial time matrix: \(A\): -, 57, 95, 150, 63, 230; \(B\): 57, -, 72, \(\infty\), 132, \(\infty\); \(C\): 95, 72, -, 289, 160, 125; \(D\): 150, \(\infty\), 289, -, 84, \(\infty\); \(E\): 63, 132, 160, 84, -, 191; \(F\): 230, \(\infty\), 125, \(\infty\), 191, - | B1 | Correct distance table. Condone dashes/crosses etc. for infinity but do not condone a 'large' number or blank cells |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| 1st iteration distance table and route table as shown, no change in first row/column, at least two values correctly reduced and two letters correctly changed | M1 | All cells complete |
| cao (full correct tables) | A1 | — |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Route must start/finish at B, E therefore consider pairings of other four odd nodes (A, C, D and F) | M1 | Either correct three pairings or recognises only A, C, D, F need consideration |
| \(AC + DF = 95 + 275 = 370\); \(AD + CF = 147 + 125 = 272^*\) | A1 | Two rows correct including pairings and totals |
| \(AF + CD = 220 + 242 = 462\) | A1 | All three rows correct including pairings and totals |
| Repeat arcs: AE, DE and CF | A1 | Selecting shortest pairing and stating these arcs should be repeated. Must be these arcs, not e.g. AED or AD via E |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Length: \(1648 + 272 = 1920\) (minutes) | B1 | cao |
# Question 4:
**(a)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Initial time matrix: $A$: -, 57, 95, 150, 63, 230; $B$: 57, -, 72, $\infty$, 132, $\infty$; $C$: 95, 72, -, 289, 160, 125; $D$: 150, $\infty$, 289, -, 84, $\infty$; $E$: 63, 132, 160, 84, -, 191; $F$: 230, $\infty$, 125, $\infty$, 191, - | B1 | Correct distance table. Condone dashes/crosses etc. for infinity but do not condone a 'large' number or blank cells |
**(b)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| 1st iteration distance table and route table as shown, no change in first row/column, at least two values correctly reduced and two letters correctly changed | M1 | All cells complete |
| cao (full correct tables) | A1 | — |
Distance table after 1st iteration:
$$A: -, 57, 95, 150, 63, 230$$
$$B: 57, -, 72, 207, 120, 287$$
$$C: 95, 72, -, 245, 158, 125$$
$$D: 150, 207, 245, -, 84, 380$$
$$E: 63, 120, 158, 84, -, 191$$
$$F: 230, 287, 125, 380, 191, -$$
**(c)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Route must start/finish at B, E therefore consider pairings of other four odd nodes (A, C, D and F) | M1 | Either correct three pairings or recognises only A, C, D, F need consideration |
| $AC + DF = 95 + 275 = 370$; $AD + CF = 147 + 125 = 272^*$ | A1 | Two rows correct including pairings and totals |
| $AF + CD = 220 + 242 = 462$ | A1 | All three rows correct including pairings and totals |
| Repeat arcs: AE, DE and CF | A1 | Selecting shortest pairing and stating these arcs should be repeated. Must be these arcs, not e.g. AED or AD via E |
**(d)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Length: $1648 + 272 = 1920$ (minutes) | B1 | cao |
---4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{43bc1e60-d8b2-4ea5-9652-4603a26c2f78-05_668_1424_169_322}
\captionsetup{labelformat=empty}
\caption{Figure 3\\[0pt]
[The total weight of the network is 1648]}
\end{center}
\end{figure}
Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road.
Floyd's algorithm is to be used to find the complete network of shortest times between the six cities.\\
An initial route matrix is given in the answer book.
\begin{enumerate}[label=(\alph*)]
\item Set up the initial time matrix.
\item Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration.
The final time matrix after completion of Floyd's algorithm is shown below.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\cline { 2 - 7 }
\multicolumn{1}{c|}{} & A & B & C & D & E & F \\
\hline
A & - & 57 & 95 & 147 & 63 & 220 \\
\hline
B & 57 & - & 72 & 204 & 120 & 197 \\
\hline
C & 95 & 72 & - & 242 & 158 & 125 \\
\hline
D & 147 & 204 & 242 & - & 84 & 275 \\
\hline
E & 63 & 120 & 158 & 84 & - & 191 \\
\hline
F & 220 & 197 & 125 & 275 & 191 & - \\
\hline
\end{tabular}
\end{center}
A route is needed that minimises the total time taken to traverse each road at least once.\\
The route must start at B and finish at E .
\item Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
\item Write down the length of the route.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 2021 Q4 [8]}}