Dijkstra's Algorithm

Dijkstra's algorithm finds shortest paths from a source in a graph with non-negative edge weights using a priority queue.

Greedy on distance

Dijkstra's algorithm computes the shortest distance from a source vertex to every other vertex when all edge weights are non-negative. It keeps a tentative distance for each vertex and repeatedly finalises the closest unfinalised vertex, then relaxes its outgoing edges, lowering neighbours' tentative distances when a shorter route is found.

Why it is correct

The key insight is that with non-negative weights, once the nearest unfinalised vertex is chosen, no later path through farther vertices could reach it more cheaply. So its tentative distance is already final. This greedy commitment is exactly what breaks if edges can be negative, which is why Dijkstra requires non-negative weights and Bellman-Ford is needed otherwise.

• Time: O((V + E) log V) with a binary-heap priority queue
• Requires non-negative edge weights
• Finds shortest paths to all vertices from one source
• A greedy algorithm proven optimal by the relaxation argument

import heapq
def dijkstra(graph, src):
    dist = {src: 0}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')): continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

The priority queue matters

A priority queue makes finding the next-closest vertex efficient. With a binary heap the cost is O((V + E) log V); with a Fibonacci heap the theoretical bound improves to O(E + V log V) by making decrease-key O(1) amortized, though the constants rarely pay off in practice.

Where it runs

Dijkstra's algorithm powers routing in road maps, network packet routing, and any weighted shortest-path query where costs are non-negative. When a good heuristic estimate of the remaining distance is available, A* extends Dijkstra to reach the goal faster.