iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Dijkstra

By · Reviewed & last updated · Part of Data Structures & Algorithms

Dijkstras algorithm finds the shortest path from a source vertex to every other vertex in a graph with non-negative edge weights. It runs in O((V + E) log V) with a binary heap and is the workhorse of routing, mapping, and many "fastest path" problems. For negative weights, switch to Bellman–Ford.

Dijkstra with a heap, reconstruction, and a road-network example

EXAMPLE
import heapq
from collections import defaultdict
from math import inf

def dijkstra(graph: dict, source):
    '''
    graph: { node: [(neighbour, weight), ...] }
    Returns (dist, prev) where:
        dist[node] = shortest distance from source
        prev[node] = previous node on the shortest path
    '''
    dist = defaultdict(lambda: inf)
    dist[source] = 0
    prev = {source: None}
    visited = set()
    heap = [(0, source)]

    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)

        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))

    return dict(dist), prev

def reconstruct(prev, target):
    path = []
    cur = target
    while cur is not None:
        path.append(cur)
        cur = prev.get(cur)
    path.reverse()
    return path

# ===== Example: city distances =====
graph = {
    'Sydney':     [('Newcastle', 162), ('Canberra', 286)],
    'Newcastle':  [('Sydney', 162),  ('Port Macquarie', 360)],
    'Canberra':   [('Sydney', 286),  ('Melbourne', 660)],
    'Melbourne':  [('Canberra', 660), ('Adelaide', 727)],
    'Adelaide':   [('Melbourne', 727)],
    'Port Macquarie': [('Newcastle', 360), ('Brisbane', 567)],
    'Brisbane':   [('Port Macquarie', 567)],
}

dist, prev = dijkstra(graph, 'Sydney')
print('Distances from Sydney:')
for city, d in sorted(dist.items(), key=lambda x: x[1]):
    print(f'  {city}: {d} km')

print('Path Sydney -> Adelaide:', reconstruct(prev, 'Adelaide'))

# ===== Early termination — stop when we pop the target =====
def dijkstra_to(graph, source, target):
    dist = {source: 0}
    prev = {source: None}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if u == target:
            return d, reconstruct(prev, target)
        if d > dist.get(u, inf): continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, inf):
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
    return inf, []

print(dijkstra_to(graph, 'Sydney', 'Brisbane'))

# ===== Common pitfalls =====
# 1) Negative weights -> Dijkstra does NOT work. Use Bellman-Ford O(VE)
#    or, if there are negative cycles, detect them with B-F.
# 2) Forgetting the visited check -> nodes get re-processed and runtime degrades.
# 3) Using a list as the priority queue -> O(V^2). Use heapq.
# 4) Updating heap entries in place -> heap invariants break.
#    Push a new (distance, node) and use the visited check to skip stale ones.

# ===== When to reach for A* instead =====
# Same algorithm + an admissible heuristic h(n) -> goal:
#     f(n) = g(n) + h(n)     instead of f(n) = g(n)
# A* expands fewer nodes when you have a good heuristic (e.g., Euclidean
# distance on a road network). Dijkstra is A* with h(n) = 0.

Why it matters

Push (cost, node) pairs and discard stale entries with a visited check — much simpler than a decrease-key heap and equally fast in practice. The runtime is still O((V+E) log V) because each edge contributes at most one heap insert.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
// Single-source shortest path on a weighted graph with no negative edges.
// Use a min-heap keyed by distance. O((V + E) log V).
Try it Yourself »

Discussion

Loading…