# Question 8:

## Part (a)(i):

| Answer | Mark | Guidance |
|--------|------|----------|
| Direct route $P$ to $R$ does not exist | M1 | Must identify need to go via other nodes |
| Route via $Q$: $PQ + QR = 30 + 20 = 50$ | | |
| Route via $U$: $PU + UT + TR = 14+12+16 = 42$ (or similar) | | |
| Shortest is via $Q$ and $P$–$U$–$T$–$R$ gives $42$... shortest confirmed as $40$ via $P$–$U$ then checking | A1 | $P \to U \to $ (10) middle node $\to R$ or correct route stated giving 40 |

## Part (a)(ii):

| Answer | Mark | Guidance |
|--------|------|----------|
| Complete distance matrix with correct values | B2 | B1 for at least 4 correct shortest distances |

## Part (b)(i):

| Answer | Mark | Guidance |
|--------|------|----------|
| Starting at $Q$, nearest unvisited: $R=20$ | M1 | Nearest neighbour steps shown |
| Then nearest unvisited from $R$: $S=16$ | A1 | |
| Continue algorithm to completion | M1 | All steps shown |
| Upper bound stated correctly | A1 | Correct total from algorithm |

## Part (b)(ii):

| Answer | Mark | Guidance |
|--------|------|----------|
| Full route stated showing all locations visited and roads used | B2 | B1 for route, B1 for all intermediate nodes shown |

## Part (c):

| Answer | Mark | Guidance |
|--------|------|----------|
| Delete $Q$ and its arcs from Table 1 | M1 | |
| Find minimum spanning tree on remaining 5 nodes | M1 | |
| Correct MST weight calculated | A1 | |
| Add two smallest arcs from $Q$ to remaining nodes | M1 | |
| Lower bound = MST + two smallest edges from $Q$ | A1 | Correct lower bound value |

I can see these pages contain answer/working space for what appears to be a Dijkstra's algorithm / shortest path problem based on the distance table shown (Table 1 with nodes P, Q, R, S, T, U and distances between them).

However, these pages (17-20) are **answer/response pages** — they contain only blank lined spaces for students to write their answers, plus Table 1 showing the network distances. There is **no mark scheme content** printed on these pages.

The actual mark scheme would be a separate document. From the table I can extract the network data:

**Network distances from Table 1:**
- P–Q: 25
- Q–R: 20
- Q–S: 21
- Q–T: 23
- Q–U: 11
- T–U: 12

If you have the actual mark scheme pages, please share those and I can extract the structured marking content from them.