Dijkstra's Algorithm

Greedy on a min-heap

Dijkstra keeps a dist[] array initialized to infinity except the source (0), and always expands the closest unvisited node next using a min-heap. Once a node is popped with its final distance, it's never revisited — this greedy choice is safe because all edge weights are non-negative.

Implementation

Push (distance, node) tuples; the heap always surfaces the smallest distance first. Skip stale entries where a shorter path was already found.

import heapq

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

Output:

# g[u] = list of (neighbour, weight)
dijkstra(5, g, 0)  # -> shortest distance from node 0 to all others

Complexity & limits

With a binary heap: O((V+E) log V). Dijkstra fails with negative edge weights — a later cheaper path can undercut an already-finalized distance. Use Bellman-Ford when negatives are possible.

Quick check

Test the key constraint.

Quick check: Dijkstra's algorithm gives correct results only when:

• The graph is undirected
• All edge weights are non-negative
• The graph has no cycles
• The graph is a tree