Mathematics Standard • Year 11 • Networks • Lesson 6
Shortest Paths · Apply
Compare weighted routes and track best-known distances with Dijkstra’s algorithm.
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 · Emergency route. Undirected travel times: HS=4, HA=2, AS=1, ST=5, AT=8, AB=3, TB=10, BN=2, TN=6. Find the shortest time from H to N. 3 marks
Q2 · Compare direct and indirect. In the same network, direct H–S takes 4 minutes. How long is H–A–S, and which is quicker? 2 marks
Q3 · Report a valid shortest route. Give the ordered path and total time from H to N. Verify each consecutive pair is an edge. 2 marks
Q1 · Emergency route
H0: A2,S4. Settle A2: S3,T10,B5. Settle S3: T8. Settle B5: N7. T8 offers 14 to N, so shortest is H–A–B–N, 7 minutes.
Q2 · Compare direct and indirect
H–A–S=2+1=3 minutes, one minute quicker than H–S.
Q3 · Report a valid shortest route
H–A–B–N, 7 minutes; HA, AB and BN are listed links.