Loading...
Dijkstra's algorithm finds the shortest path from a source to every node in a graph with non-negative edge weights. It repeatedly locks in the closest unvisited node and relaxes its outgoing edges, updating tentative distances. It is the backbone of GPS routing and network path-finding. With a binary heap it runs in O((V + E) log V).
Finds shortest paths from a source by always expanding the closest node.
Distance to A = 0; every other node = ∞.
| Average case | O((V + E) log V) |
| Worst case | O(V²) |
| Space | O(V) |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
import math
def dijkstra(adj, src):
n = len(adj)
dist = [math.inf] * n
visited = [False] * n
dist[src] = 0
for _ in range(n):
u = -1
for i in range(n): # pick the closest unvisited node
if not visited[i] and (u == -1 or dist[i] < dist[u]):
u = i
if u == -1 or dist[u] == math.inf:
break
visited[u] = True
for v, w in adj[u]: # relax each edge out of u
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return distRunning Dijkstra's Shortest Path on the sample graph, step by step:
The control flow of the algorithm as a diagram: