Every time a navigation app finds the fastest route between two points on a road network with dozens of possible paths, some variant of an algorithm devised by Edsger Dijkstra in 1956 is very likely doing the work behind the scenes. Dijkstra's algorithm is elegantly simple in principle — always explore outward from whichever reachable point currently has the lowest known total cost — and it's provably guaranteed to find the true shortest path, with exactly one important condition it depends on to make that guarantee hold.
Always expand the cheapest option you haven't settled yet
Starting from a source point, Dijkstra's algorithm keeps track of the shortest known distance to every point in the network reached so far, updating those distances as it explores. At each step, it picks the unvisited point with the smallest known distance, marks it as settled (its shortest distance is now final), and checks whether reaching its neighbours through it would be cheaper than any route already known to them. Repeat this greedy "always take the cheapest next step" process until the destination is settled, and the result is guaranteed to be the actual shortest path — not just a plausible-looking one — which is what makes the algorithm trustworthy enough to build real routing systems on top of.
Negative weights break the greedy guarantee
Dijkstra's algorithm depends on one crucial assumption: every edge in the network has a non-negative cost. The reasoning behind why negative weights break it is straightforward once you see it — the algorithm settles a point's shortest distance permanently once found, assuming no later discovery could possibly make an already-settled path even shorter. If some edge could have a negative cost, that assumption fails: a path through a point already marked "settled" could later turn out to be cheaper after all, thanks to a negative-cost shortcut the algorithm had no way to anticipate. Networks that genuinely need negative edge weights — modelling costs that can decrease a total, such as certain financial or currency-arbitrage networks — require a different algorithm, like Bellman-Ford, which handles negative weights correctly by allowing points to be re-examined and updated, at the cost of running more slowly than Dijkstra's algorithm on ordinary networks.
What we're still unsure about
Dijkstra's algorithm and its correctness guarantee under non-negative weights are completely settled, rigorously proven computer science — there's no dispute about how or why it works. What continues to be an active area of practical engineering is squeezing more real-world performance and precision out of routing at massive scale: modern navigation systems layer heuristics, precomputed shortcuts, and traffic-aware cost adjustments on top of the basic shortest-path idea, and getting all of that to run fast enough for millions of simultaneous route requests, while staying accurate as real-time conditions change, remains a genuinely hard systems engineering problem distinct from the underlying algorithm's own mathematics.
This sits inside Graph Algorithms (Dijkstra, Bellman-Ford, Kruskal), one of eight topics in Algorithms, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.