Shortest paths
Objective. Apply Dijkstra's algorithm to a weighted graph.
- 1. Learn
- 2. Worked example
- 3. Practice
- 4. Feedback
- 5. Continue
Learn: the key idea
Keep a tentative distance for each vertex, always finalise the smallest unvisited one, then relax its neighbours. It requires non-negative weights.
Worked example
From A: A→B is 2, A→C is 5, B→C is 1. Shortest A to C?
- 1Via A→C directly: 5.
- 2Via A→B→C: 2 + 1 = 3.
- 33 is smaller.
Answer: 3, via B
Concept mastery
Based on your past attempts at this lesson — the question types to practise again come first.
Complete a practice set to see your concept breakdown here.
Practice
Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.
Start practisingCommon mistake. Finalising a vertex before all shorter routes to it have been considered.
Your progress
Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.
0 of 5 steps complete
Your place saves automatically as you read.