AdvancedGraphs

Dijkstra: shortest paths with weights

Always expand the closest unfinished node next, using a min-heap of (distance, node). Works for non-negative weights only.

The idea

With weighted edges, BFS's “fewest edges” isn't the cheapest path. Dijkstra keeps a min-heap of tentative distances and always finalizes the closest node; with non-negative weights nothing found later can beat it.

Skip heap entries that are stale (a shorter distance was already found).

Worked example

Network Delay Time from node 2

heap [(0, 2)] → finalize 2 at 0, push its neighbours with their edge times
pop the smallest each time, relax its edges
The answer is the largest finalized distance, or −1 if a node is unreachable.

In code (Python)

import heapq

def dijkstra(graph, source):          # graph: node -> [(neighbour, weight)]
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float("inf")):
            continue                   # stale entry
        for nxt, w in graph.get(node, []):
            nd = d + w
            if nd < dist.get(nxt, float("inf")):
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))
    return dist

O((V + E) log V) time, O(V) space.

How to spot it

Weighted graph + “minimum cost / time / delay”, all weights ≥ 0.

Common mistakes

Using it with negative weights (use Bellman-Ford).
Not skipping stale heap entries, which wastes time.

Practise it

Go further

Up next for you · Beginner

“Have I seen this?” is a set →

All tips