Dijkstra's Algorithm: Shortest Paths with Nonnegative Weights

Keep extending the cheapest known route

Imagine you are finding the cheapest way to travel from one starting point to every other point. Keep a tentative price for each place: zero for the start, infinity for everywhere else. Each time you reach a place, check whether going from there to one of its neighbors makes that neighbor cheaper to reach. If it does, replace the old price. This improvement is called relaxing an edge.

A min-priority queue helps select the not-yet-settled place with the smallest tentative distance. Once that place is removed from the queue, its distance is final: with nonnegative edge weights, a route that takes a detour cannot come back with a smaller total. This is why Dijkstra's algorithm requires nonnegative weights.

The graph can be directed or undirected. For an undirected graph, treat each edge as two directed connections with the same weight.

Worked example: shortest route from S to D

Consider these directed, nonnegative edges: S→A (4), S→B (1), B→A (2), A→C (1), B→C (5), A→D (7), and C→D (3). Start with distance 0 at S and infinity elsewhere. The table shows the changes as the closest unsettled vertex is selected.

The resulting shortest route is S → B → A → C → D, with total weight 1 + 2 + 1 + 3 = 7. The direct edge from A to D costs 7 by itself, so that route from S would cost 10; comparing complete route costs is what matters.

Python implementation

import heapq
from math import inf

def dijkstra(graph, source):
    distance = {node: inf for node in graph}
    distance[source] = 0
    heap = [(0, source)]
    while heap:
        cost, node = heapq.heappop(heap)
        if cost != distance[node]:
            continue  # ignore an outdated heap entry
        for neighbor, weight in graph[node]:
            candidate = cost + weight
            if candidate < distance[neighbor]:
                distance[neighbor] = candidate
                heapq.heappush(heap, (candidate, neighbor))
    return distance

Many standard heaps do not support decrease-key, so this implementation inserts an improved pair and skips stale entries when they are later popped. To reconstruct a path, also store parent[neighbor] = node whenever the distance improves, then follow parents backward from the destination.

When to use Dijkstra, and its complexity

Use Dijkstra when you need shortest paths from one source in a weighted graph with nonnegative edge costs—for example, choosing a lowest-cost route or minimizing travel time. With adjacency lists and a binary min-heap, it takes O((V + E) log V) time and O(V + E) space, including the graph. If you only need one destination, you can stop as soon as it is settled.

For an unweighted graph, use BFS instead: it minimizes the number of edges in O(V + E) time. If any edge may be negative, use Bellman–Ford or another algorithm designed for negative weights; Dijkstra can settle a vertex before its best route is discovered. Unreachable vertices keep an infinite distance.