What you'll learn

  1. Quick answer
  2. The idea in one sentence
  3. The implementation
  4. Why a priority queue, and the lazy deletion trick
  5. Why negative weights break it
  6. Where it is actually used, and variants
  7. FAQ

Quick Answer

Repeatedly take the unvisited node with the smallest known distance, and use it to improve its neighbours' distances. A priority queue makes picking that node fast. It does not work with negative edge weights.

The idea in one sentence

Keep a best-known distance to every node, starting at infinity except the source at zero. Repeatedly pick the closest unvisited node, and check whether going through it gives a shorter route to each of its neighbours. Mark it visited and continue.

The crucial insight is why marking visited is safe. When you pick the closest unvisited node, no later path can reach it more cheaply — any other route would have to pass through a node that is already further away, and distances only increase as you add edges.

That argument depends entirely on edge weights being non-negative, which is exactly why the algorithm breaks when they are not.

The implementation

import heapq

def dijkstra(graph, start):
    dist = {n: float('inf') for n in graph}
    dist[start] = 0
    pq = [(0, start)]
    visited = set()

    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

On this graph:

graph = {
  'A': [('B',4), ('C',2)],
  'B': [('C',5), ('D',10)],
  'C': [('E',3)],
  'D': [('F',11)],
  'E': [('D',4)],
  'F': []
}

print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}

Note D is 9, not 10. The direct edge B→D costs 10, but going A→C→E→D costs 2+3+4 = 9. Finding that indirect improvement is the whole point.

Why a priority queue, and the lazy deletion trick

The step "pick the closest unvisited node" is done thousands of times. Scanning every node each time makes the algorithm O(V²). A min-heap makes it O((V+E) log V), which is the difference between usable and not on a large graph.

Two details in the code that look odd and are deliberate:

Tuples in the heap. heapq orders tuples by first element, so (distance, node) automatically gives a min-heap by distance.

The if u in visited: continue line. When a node's distance improves, we push a new entry rather than updating the old one — Python's heapq has no decrease-key operation. So the heap accumulates stale entries. Skipping already-visited nodes discards them harmlessly. This is called lazy deletion, and it is the standard approach.

Why negative weights break it

Dijkstra commits to a node's distance the moment it is visited, on the reasoning that nothing can improve it later. A negative edge invalidates that reasoning.

Imagine A→B costs 5, A→C costs 10, and C→B costs −8. Dijkstra visits B first at distance 5 and finalises it. But A→C→B costs 10 − 8 = 2, which is cheaper. The answer is simply wrong, and there is no warning.

For graphs with negative weights use Bellman-Ford, which is slower at O(V·E) but handles them and can also detect negative cycles — where no shortest path exists because you can loop forever getting cheaper.

This is a favourite interview follow-up. "Would Dijkstra work here?" on a graph containing a negative edge is a trap worth recognising.

Where it is actually used, and variants

Road and transit routing is the obvious case, though real map services use heavily optimised variants. Network routing protocols use it to compute link costs. Anywhere you have a weighted graph and need cheapest paths, it applies.

Useful variations worth knowing:

  • Reconstructing the path, not just the distance — keep a prev dictionary recording which node you came from, then walk backwards from the destination.
  • Stopping early when the destination is popped, if you only need one target rather than all.
  • A* — Dijkstra plus a heuristic estimate of remaining distance, which explores far fewer nodes when you have a sensible estimate such as straight-line distance.
  • BFS is the unweighted case. If every edge costs 1, plain breadth-first search gives the same answer with no heap needed.

That last point is worth remembering: reaching for Dijkstra on an unweighted graph is over-engineering.

Frequently Asked Questions

Why does Dijkstra not work with negative weights? It finalises a node's distance when visited, assuming no later path can improve it. A negative edge can make a longer-looking route cheaper, so that assumption fails and the result is silently wrong.
What is the time complexity? O((V + E) log V) using a binary heap, where V is nodes and E is edges. Without a priority queue it degrades to O(V²), which still beats the heap version on very dense graphs.
Why push duplicate entries into the heap? Python's heapq cannot decrease an existing key, so the standard approach is to push the improved distance and skip stale entries when popped. This is called lazy deletion.
What is the difference between Dijkstra and BFS? BFS finds shortest paths when every edge costs the same, using a plain queue. Dijkstra handles differing edge weights using a priority queue. On an unweighted graph they give the same answer.
How do I get the actual path, not just the distance? Keep a dictionary recording the previous node each time you improve a distance, then walk backwards from the destination to the source and reverse the result.