Dijkstra - Implementation

Here is the complete Dijkstra algorithm:

function dijkstra(graph, source):
    dist[source] = 0
    for all other v: dist[v] = infinity

    pq = min-heap with (0, source)

    while pq not empty:
        (d, u) = pq.pop()
        if d > dist[u]: continue

        for each neighbor v with weight w:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pq.push((dist[v], v))

    return dist

The if d > dist[u]: continue line skips outdated entries. When you push a better distance, the old entry stays in the heap. This check filters it out.

This runs in $O((V + E) \log V)$ time and uses $O(V)$ space.