Dijkstra's Algorithm

In Turkish: Dijkstra Algoritması
Pronunciation: DYKE-struhz AL-guh-rith-um

Updated September 30, 20263 min read

In short

Dijkstra's algorithm is a graph algorithm that finds the shortest paths from a starting node to every other node when all edge weights are zero or positive.

What is Dijkstra's algorithm?

Dijkstra's algorithm finds the cheapest path from one starting node to every other node in a weighted graph, where each edge has a cost such as distance, time, or price. It was published by the Dutch computer scientist Edsger W. Dijkstra in 1959 and is still one of the most widely used algorithms in computing. It only works when no edge has a negative weight.

The algorithm keeps a tentative distance for every node, starting at 0 for the source and infinity for everything else, plus a priority queue of nodes ordered by that distance. It repeatedly takes the unvisited node with the smallest distance, whose distance is now final, and relaxes each of its edges: if going through this node gives a neighbor a shorter distance than the one recorded, it updates the neighbor and pushes it onto the queue. With a binary heap as the priority queue, it runs in O((V + E) log V) time, where V is the number of vertices and E the number of edges. Recording which node each improvement came from lets you rebuild the actual route at the end.

Picture water poured in at the starting point of a network of pipes of different lengths: it reaches nearby junctions first and spreads outward, and the moment it arrives at a junction, it has taken the shortest route there. Dijkstra's algorithm, or faster variants built on it, powers route planning in maps and navigation apps, link-state routing protocols such as OSPF, which routers use to compute paths through a network, and pathfinding in games and robotics. The A* algorithm extends it with a heuristic, an estimate of the remaining distance, to steer the search toward one goal and explore fewer nodes.

Dijkstra's algorithm is often compared with breadth-first search. BFS finds the path with the fewest edges and is the right tool when every edge costs the same, while Dijkstra's algorithm accounts for different weights; with all weights equal to 1, the two give the same answers. It also fails with negative edge weights, because it assumes a node's distance is final once visited, so those graphs need the slower Bellman-Ford algorithm. It is a greedy algorithm, since it always commits to the closest unvisited node, but unlike many greedy methods it is proven to give the optimal answer.

Key takeaways

Dijkstra's algorithm finds the shortest paths from one source to all other nodes in a weighted graph.
It requires every edge weight to be zero or positive.
It repeatedly finalizes the closest unvisited node and relaxes that node's edges.
With a binary heap, it runs in O((V + E) log V) time.
BFS is enough when all edges cost the same, and A* adds a heuristic to reach a single target faster.

Example

Dijkstra's algorithm with a heap in Pythonpython

import heapq
def dijkstra(graph, source):
    dist, queue = {source: 0}, [(0, source)]  # queue holds (distance so far, node)
    while queue:
        d, node = heapq.heappop(queue)  # the closest node not yet finalized
        if d > dist[node]:
            continue  # a stale entry: a shorter path was already found
        for neighbor, weight in graph[node]:
            if d + weight < dist.get(neighbor, float("inf")):
                dist[neighbor] = d + weight  # relax the edge
                heapq.heappush(queue, (d + weight, neighbor))
    return dist

roads = {"A": [("B", 5), ("C", 2)], "B": [("D", 4)], "C": [("B", 1), ("D", 8)], "D": []}
print(dijkstra(roads, "A"))  # {'A': 0, 'B': 3, 'C': 2, 'D': 7}

Readers ask

Why doesn't Dijkstra's algorithm work with negative weights?

It assumes that once a node is taken from the priority queue, its distance is final, because any other route would have to be longer. A negative edge found later could make another route shorter and break that assumption, so graphs with negative weights need the Bellman-Ford algorithm instead.

What is the difference between Dijkstra's algorithm and BFS?

BFS finds the path with the fewest edges, which is the shortest path only when every edge costs the same. Dijkstra's algorithm takes edge weights into account and uses a priority queue instead of a plain queue; with all weights equal, both give the same result.

What is the time complexity of Dijkstra's algorithm?

With a binary heap, it runs in O((V + E) log V) time, where V is the number of vertices and E the number of edges. A simple array-based version runs in O(V^2), which can be better for very dense graphs.