Quick questions on Shortest path problems in networks for HSC Maths Standard 2

Given a weighted graph with vertices and edge weights (distances, times, costs), find the path from a starting vertex to an ending vertex with the smallest total weight.

For small networks (say $5$ vertices or fewer), list all sensible candidate paths between the start and end vertex, compute each total weight, and pick the smallest.

For larger networks, use systematic labelling:

While labelling, record the predecessor: which vertex you came from when you set the current label. After finishing, trace backwards from the end vertex to the start using these predecessors, then reverse to get the path in forward order.

If two paths have the same total weight, there are multiple shortest paths. State both (or all) in your answer.

:::worked Worked example ### Inspection on a small graph

Starting from $A$. Label $A = 0$. Others $\infty$.

Suppose Sydney transport edges (in minutes):

When using inspection, check all branching combinations. Even visually-unappealing paths sometimes turn out to be shortest.

In systematic labelling, you must update a neighbour's label whenever you find a shorter path. Once finalised, the label cannot change.

Record which vertex you came from when each label was last updated.

MST connects all vertices with minimum total weight. Shortest path finds the cheapest route between two specific vertices. Different problems, different algorithms.