Discrete Math › Section C · Graph theory › Topic C.10
Weighted graphs and shortest paths
Every route-planning app answers the same question thousands of times a second: what is the cheapest way from here to there? Breadth-first search answers it when every step costs the same, and Dijkstra's algorithm answers it when steps have different, non-negative costs.
In this topic
- Costs on the edges
- Equal costs: breadth-first search
- Dijkstra's idea
- The algorithm in steps
- Worked example: tracing Dijkstra
- Reading off the route
- Why finished means final
- Worked example: a negative weight breaks it
- Beyond one starting point
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…