Overview
Dijkstra's Algorithm finds the shortest path from a start node to every other node in a graph with non-negative edge weights. It always expands the unvisited node with the smallest known distance, gradually locking in optimal distances outward from the start.
It generalises BFS to weighted graphs by using a priority queue keyed on cumulative distance instead of a plain FIFO queue, so terrain with varying movement costs is handled correctly.
How Dijkstra's Algorithm works
- Set the start's distance to 0 and every other node's distance to infinity.
- Pull the unvisited node with the smallest distance from a priority queue.
- Relax each neighbour: if going through the current node is shorter, update the neighbour's distance and parent.
- Mark the current node finalised and repeat until the goal is settled, then trace the parents back into a path.
When to use it
- Shortest routes on weighted graphs such as road networks or grids with terrain costs.
- Network routing, where link latency or cost varies between hops.
- Use A* instead when a good heuristic can steer the search toward a single goal faster.
Complexity analysis
With a binary-heap priority queue Dijkstra runs in O((V + E) log V): each edge may trigger a heap update and each vertex is extracted once. Space is O(V) for distances and the queue. Because it only relaxes with non-negative weights, it never revisits a finalised node — but it also cannot handle negative edges.
Frequently asked questions
Why can't Dijkstra handle negative edge weights?
It assumes that once a node is finalised with the smallest distance, no later path can improve it. A negative edge could make a longer-looking route cheaper afterwards, breaking that assumption — use Bellman-Ford for negative weights.
How does Dijkstra relate to BFS and A*?
Dijkstra is BFS extended to weighted graphs via a priority queue, and A* is Dijkstra plus a heuristic estimate of the remaining distance. With a zero heuristic, A* behaves exactly like Dijkstra.