Weighted graphs and shortest path – Dijkstra's algorithm
MathematicsSets, Logic & Graph TheoryAges 16–17
Use it with your class: students open it from a link or a QR code, with no account needed.
Next in Sets, Logic & Graph Theory
A map of locations is modeled as a graph: vertices are places, edges are roads, and weights are distances in kilometers. Choose a start vertex and an end vertex, then step through Dijkstra's algorithm: assign temporary labels, fix the vertex with the smallest label, and update its neighbors. Click an edge to change its length (a detour or a closed road) and watch the shortest path change, along with vertex degrees and the condition for an Eulerian circuit.
Lesson: Introduction to graph theory
What it shows
Road networks can be modelled as weighted graphs: vertices are places, edges are roads and each weight is a distance in kilometres. Dijkstra's algorithm finds shortest paths from a start vertex by keeping a temporary distance label on every vertex, repeatedly fixing the unfixed vertex with the smallest label and updating the labels of its neighbours. Because every weight is positive, a fixed label can never be improved later. The simulation also shows vertex degrees, whose sum is twice the number of edges and which, in a connected graph, decide whether Eulerian paths and circuits exist.
How to use
Choose a Map, then pick the start and destination in From and To. Press Next step repeatedly and ask students to predict which vertex will be fixed next and which labels will change; use Previous step to revisit a decision. Compare the finished route with the route that uses the fewest roads. Then set Click an edge to block / open road, close a road on the shortest path and press Run all to see the new route.
Parameters you can change
- Map Town (7 locations), Province districts (9 locations)
- Start vertex
- End vertex
Questions to explore
- Why is a vertex's label never changed again once it has been fixed?
- Is the route with the fewest edges always the shortest route, and which example on the map shows this?
- Which roads could you block so that the remaining roads stay connected and the graph has an Eulerian circuit?
