Mathematics Standard • Year 11 • Networks • Lesson 6
Shortest Paths · Build
Run Dijkstra’s algorithm from a chosen start vertex using non-negative edge weights.
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 · Dijkstra worked example. Undirected weights: AB=4, AC=2, BC=1, BD=5, CD=8, BE=3, CE=10, EF=2, DF=6. Run from A until F is permanent. 3 marks
Q2 · Update through B. When B becomes permanent at 3, what candidate distances are offered to D and E? 2 marks
Q3 · Non-negative weights. Why does Dijkstra require non-negative edge weights? 2 marks
Q1 · Dijkstra worked example
A0: B4,C2. Settle C2: B3,D10,E12. Settle B3: D8,E6. Settle E6: F8. F has distance 8 via A–C–B–E–F (2+1+3+2). D is also tentatively 8, so either tied vertex may be settled first; F’s shortest distance remains 8.
Q2 · Update through B
D gets 3+5=8; E gets 3+3=6. These improve tentative values 10 and 12.
Q3 · Non-negative weights
With non-negative weights, extending a path cannot make it shorter, so a smallest tentative distance is safe to make permanent. Negative edges would break that guarantee.