computer science//algorithms//graph search//Dijkstra's algorithm

2026-07-14

Dijkstra's algorithm is an uninformed graph search algorithm that finds the least-cost paths from one start node to every other node by always expanding the closest node not yet settled, and it is used wherever routes must be computed without any estimate of where the goal lies: network routing, road maps, a robot planning to several destinations at once. Link-state routing protocols such as OSPF run it in every router to build their forwarding tables.

It grows outward from the start like an oil stain spreading on a floor. Every node keeps the best cost found so far; the algorithm takes the node with the smallest one, declares that cost final, and relaxes its neighbours (if going through this node is cheaper than their current best, it replaces it). Because costs only add up, the first time a node is taken out its cost cannot be beaten later. On a warehouse grid this means rings of equal travel time around the robot, expanding the same way toward the goal and away from it.

It is A* search with the heuristic set to zero. The stain spreads evenly in every direction because nothing tells it where the goal is, which costs many more expansions than A* when a good estimate of the remaining distance exists. When no such estimate exists, or when the paths to all destinations are wanted from a single run, Dijkstra is the right tool.

It requires edge costs that are never negative. A negative edge could make a settled node cheaper after the fact, and the guarantee breaks (Bellman-Ford handles that case at a higher price). Distances, times and energies are naturally nonnegative, so in robotics this is rarely a limit.

With a binary heap for the frontier it costs about O((V+E)log⁡V)O((V+E)\log V)O((V+E)logV) for VVV nodes and EEE edges, cheap enough for a building floor plan at every replanning cycle, but it suffers the same explosion as every grid method once the state has many dimensions (curse of dimensionality).