Dijkstra's Algorithm

Dijkstra’s algorithm finds shortest paths from one start vertex in a weighted graph with non-negative edge weights.

It combines greedy selection with a priority queue.

Core Idea

The algorithm repeatedly processes the not-yet-finalized vertex with the smallest known distance. With non-negative weights, once that vertex is chosen, no later path can improve it.

Neighbors are relaxed by checking whether going through the current vertex gives a smaller distance.

Python Example

import heapq
 
def dijkstra(graph, start):
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
    heap = [(0, start)]
 
    while heap:
        current_distance, node = heapq.heappop(heap)
        if current_distance != distance[node]:
            continue
 
        for neighbor, weight in graph[node]:
            new_distance = current_distance + weight
            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                heapq.heappush(heap, (new_distance, neighbor))
 
    return distance

The heap chooses the currently smallest known distance.

Common Confusions

Dijkstra’s algorithm does not handle negative edge weights correctly in general.

Python’s heapq does not decrease a key in place. A common pattern is to push a new entry and ignore stale entries when they are popped.

When To Use It

Use Dijkstra when edge weights are non-negative and the problem asks for shortest cost, time, distance, or risk from one start.