Mathematics Standard • Year 11 • Networks • Lesson 6
Shortest Paths · Master
Complete Dijkstra’s table, track predecessors and interpret tied routes.
Practice
Unless a question says otherwise, treat each network as a simple undirected graph: edges are unordered vertex pairs, with no loops or duplicate edges. Show your reasoning in the answer space; an edge list is enough.
Q1 · Work the table. Undirected weights: PQ=3, PR=1, RQ=1, QS=4, RS=5, RT=8, QT=7, ST=2. Run Dijkstra from P to T. 3 marks
Q2 · Explain equal candidates. At Q, both P–R–S and P–R–Q–S have length 6. Why keep 6 rather than adding values? 2 marks
Q3 · Model limitation. What must be added to answer “which route is safest” when the network only gives distances? 2 marks
Q1 · Work the table
P0: Q3,R1. Settle R1: Q2,S6,T9. Settle Q2: S6,T9. Settle S6: T8. Shortest path P–R–S–T has length 8.
Q2 · Explain equal candidates
Distance labels are lengths of separate routes, not counts to add. Keep the minimum distance; equal routes are alternatives.
Q3 · Model limitation
Safety weights/ratings or another stated constraint are needed. Distance weights alone answer which route is shortest.