Shortest paths

A shortest-path algorithm finds the cheapest route between points in a graph where each edge has a cost, like driving times on a road map. Dijkstra’s algorithm is the workhorse: it keeps a priority queue of tentative distances and repeatedly locks in the closest unfinished node, which is correct as long as no edge has a negative cost. Bellman–Ford handles negative edges by relaxing every edge in repeated rounds, and can detect a negative cycle. Floyd–Warshall computes distances between all pairs at once. A* speeds up a single search by using an estimate of the remaining distance to steer toward the goal. Maps, network routing and game pathfinding all rely on these.