Dijkstra's Shortest Path Algorithm
A greedy graph algorithm that finds the shortest paths from a single source vertex to all others in graphs with non-negative edge weights.
Dijkstra's algorithm solves the single-source shortest path problem: given a graph with weighted edges and a starting vertex, it computes the shortest possible distance to every other reachable vertex. It was conceived in 1956 by the Dutch computer scientist Edsger W. Dijkstra and published in 1959. The algorithm requires that all edge weights be non-negative, which holds for most practical routing and network problems.
The algorithm is greedy. It keeps a tentative distance for every vertex, initially zero for the source and infinity for all others. In each step it selects the unvisited vertex with the smallest tentative distance, marks it as settled, and "relaxes" each of its outgoing edges: if the path through the settled vertex improves a neighbor's tentative distance, the neighbor's distance is updated. Because settled vertices are chosen in increasing distance order, each vertex is finalized exactly once.
A min-heap priority queue makes the selection step efficient. Each relaxation may insert or decrease a key in the heap, which costs O(log V) per operation. With V vertices and E edges the total running time is therefore O((V + E) log V) with a binary heap, and O(V^2) if an ordinary array is used on dense graphs. The cost class is analyzed with Big O notation.
function dijkstra(graph, source):
dist[source] = 0
for each vertex v != source: dist[v] = infinity
pq = min-heap of (dist[v], v), starting with (0, source)
while pq is not empty:
(d, u) = pq.pop_min()
if d > dist[u]: continue // stale entry, skip
for each edge (u, v, weight):
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
pq.push((dist[v], v))
return dist
The algorithm fails on graphs with negative edge weights, because a negative edge can reduce a settled vertex's distance after it has already been finalized; for such graphs the Bellman–Ford algorithm is the standard alternative. Variants of Dijkstra's algorithm are embedded in road navigation systems, in the OSPF and IS-IS link-state routing protocols used inside networks, and in many graph-analysis libraries.
Tags
algorithms graph theory priority queue shortest path