Dijkstra's Shortest Path
DSA · Graphs
Theory
Dijkstra's algorithm finds the shortest distance from a source to every vertex in a graph with non-negative edge weights. It keeps tentative distances, repeatedly picks the unvisited vertex with the smallest distance (using a priority queue), and relaxes its edges: if going through this vertex gives a shorter path to a neighbour, the neighbour's distance is updated. With a binary heap it runs in O((V + E) log V).
Why we use it
It is the standard algorithm for road navigation, network routing and any weighted shortest-path problem without negative weights.
When to use it
Use it for maps and GPS, network latency routing, cheapest flights, and game path costs. Do not use it with negative weights; use Bellman-Ford instead.
How it works
- dist[source] = 0, others infinity; heap = [(0, source)]
- Heap empty? Yes: Done. No: Pop node u with smallest distance.
- For each edge u -> v with weight w
- dist[u] + w < dist[v]? Yes: Update dist[v], push (dist[v], v). No: Skip.
- dist holds shortest distances (non-negative weights)
Syntax
dist[source] = 0, others = infinity
while unvisited remain:
u = unvisited vertex with smallest dist
for v, w in graph[u]:
if dist[u] + w < dist[v]: dist[v] = dist[u] + w
Time: O((V+E) log V) with a heapExample
graph = {
"Home": [("Mall", 4), ("Office", 1)],
"Office": [("Mall", 2), ("Gym", 5)],
"Mall": [("Gym", 1)],
"Gym": [],
}
def dijkstra(src):
dist = {v: float("inf") for v in graph}
prev = {}
dist[src] = 0
unvisited = set(graph)
while unvisited:
u = min(unvisited, key=lambda v: dist[v])
unvisited.remove(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
return dist, prev
dist, prev = dijkstra("Home")
print("Distances:", dist)
path, node = [], "Gym"
while node != "Home":
path.append(node); node = prev[node]
print("Best route:", " -> ".join(["Home"] + path[::-1]))Key points
- Non-negative weights only
- Always expands the closest unvisited vertex
- Relax edges to improve distances
- Use a heap for O((V+E) log V)