§-Quick questions
NSWMaths Standard 2Year 12: Networks
Quick questions on Shortest path problems in networks for HSC Maths Standard 2
4short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.
Why do you always finalise (lock in) the smallest unfinalised label?Show answer
Because nothing left in the graph can reach it for less. Any other route to it would first pass through a vertex whose label is the same or bigger. All the edge weights are positive, so going that way can only add more.
What are equal-weight ties?Show answer
If two paths have the same total weight, there are multiple shortest paths, and the run above is a clean example: --- and ---- both total . Systematic labelling reports only one of them (whichever it recorded first), so a tie is easy to miss. When a question asks for "the" shortest path and a tie exists, state every tied route; when it asks only for the shortest distance, the single value is enough. The tell-tale sign of a tie is the moment in stage 3 where the route - re-derives 's existing label exactly rather than beating it.
What is checking you have not missed a shorter route?Show answer
The most common worry with inspection is "could there be a shorter path I did not list?" Three checks settle it:
What is wrong predecessor when tracing back?Show answer
Record which vertex you came from when each label was last updated, then trace and reverse.
Have a question we have not covered?
This dot-point answer is short enough that we have not extracted many short questions yet. Read the full dot-point answer or ask Mo, our study assistant, in the chat for follow ups.