# Question 3:

## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Fourth iteration updates using vertex 4 as intermediate | M1 | |
| Correct updated distance matrix entries | A3 | One mark per correct row/column updated |
| Correct updated route matrix entries | A3 | |

## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Distance from 1 to 3: read off matrix = 10 | B1 | |
| Use route matrix: $R(1,3)=2$, so go via 2; $R(1,2)=2$, $R(2,3)=3$ | M1 A1 | |
| Route: $1 \to 2 \to 3$ (or with intermediate nodes traced) | A1 | |

## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Complete network drawn with correct shortest distances between all pairs | B1 | |

## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Nearest neighbour from 1: correct sequence identified | M1 | |
| Hamilton cycle and length stated | A1 | |
| Corresponding route through original network | A1 | |

## Part (v)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Remove vertex 2 and find minimum spanning tree of remainder | M1 | |
| Add two smallest arcs incident to vertex 2 | M1 | |
| Correct lower bound calculated | A1 | |

## Part (vi)
| Answer | Marks | Guidance |
|--------|-------|----------|
| If upper bound = lower bound, optimal solution found; otherwise bounds give range | B1 | |
| Comment on whether solution is optimal | B1 | |

---