Dijkstra and Bellman-Ford find least-cost paths.
Dijkstra's algorithm finds shortest paths from a source with non-negative weights using a priority queue in O((V+E) log V). Bellman-Ford handles negative weights in O(VE); A* uses a heuristic; Floyd-Warshall computes all pairs in O(V³).
GPS navigation uses Dijkstra/A* variants on road graphs.
Shortest path algorithms find the cheapest route through a network, which is needed for navigation, routing and planning.
Dijkstra and Bellman-Ford find least-cost paths.
Shortest path algorithms find the cheapest route through a network, which is needed for navigation, routing and planning.
Dijkstra is faster but requires non-negative edge weights. Bellman-Ford handles negative weights and can detect negative cycles.
Trying every path is impossible for large networks, so systematic methods that track the best distance found so far are needed.
Typical applications include finding the quickest driving route on a road map, routing packets through a computer network and planning the lowest-cost delivery sequence across depots.
Study "BFS and DFS" first (topic 26 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Relaxation. Negative cycles. Used in GPS routing.
GPS navigation uses Dijkstra/A* variants on road graphs.
The next topic is "Minimum spanning trees", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 27 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.