# Question 5:

## Part (i)
Network drawn with 7 nodes A–G and edges with weights as given in table | B3 | B1 per 2 correct arcs, penalise missing/extra arcs

## Part (ii)
Dijkstra's algorithm from G:

| Vertex | Order | Permanent label |
|---|---|---|
| G | 1 | 0 |
| A | 2 | 5 |
| F | 3 | 8 |
| B | 4 | 16 |
| E | 5 | 14 |
| C | 6 | 15 |
| D | 7 | 17 |

Route: G → A → F → C → D, total weight = **17** | M1 for starting Dijkstra correctly | A1 for correct order of permanent labelling | A4 for fully correct labels and route

## Part (iii)
Route G → A → F → E → D (or G → B → D etc.): inspect to find route where minimum arc weight is maximised.
Route: **G–A–F–E–D**, minimum arc weight = **6** | B1 for correct route | B1 for minimum arc weight = 6 | B1 for application (e.g. width/capacity of road for wide vehicles, pipe capacity)

## Part (iv)
Modification: working value at each vertex = maximum of minimum arc weights on any path to that vertex. Update: when vertex $v$ is permanently labelled with value $p$, for each neighbour $w$ update working value as $\max(\text{current working value of } w,\ \min(p, \text{weight}(v,w)))$. Select next vertex: choose the vertex with the **largest** working value to permanently label | B1 for update rule | B1 for taking min with arc weight | B1 for taking max with current working value | B1 for selecting largest working value

---