Dijkstra's Algorithm: Shortest Path with a Priority Queue

Dijkstra’s algorithm finds the shortest path from one source vertex to every other vertex in a weighted graph with non-negative edge weights. It greedily settles the closest unsettled vertex, then relaxes its edges — updating a neighbor’s distance if going through the current vertex is cheaper. With a priority queue (min-heap) it runs in O((V + E) log V).

How it works

Set dist[source] = 0 and every other distance to infinity.
Push (0, source) into a min-heap keyed by distance.
Pop the vertex u with the smallest tentative distance. If it’s stale (the popped distance is larger than the recorded one), skip it.
Relax each edge u → v: if dist[u] + weight < dist[v], update dist[v] and push (dist[v], v).
Repeat until the heap is empty. The first time a vertex is popped, its distance is final.

#include <vector>
#include <queue>
#include <climits>

// graph[u] = list of (neighbor, weight)
std::vector<long long> dijkstra(
        const std::vector<std::vector<std::pair<int,int>>>& graph, int src) {
    int n = graph.size();
    const long long INF = LLONG_MAX;
    std::vector<long long> dist(n, INF);
    using P = std::pair<long long,int>;            // (distance, vertex)
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                 // stale entry, skip
        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {           // relaxation
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// graph.get(u) = list of int[]{neighbor, weight}
long[] dijkstra(List<List<int[]>> graph, int src) {
    int n = graph.size();
    long[] dist = new long[n];
    Arrays.fill(dist, Long.MAX_VALUE);
    // min-heap of long[]{distance, vertex}
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    dist[src] = 0;
    pq.add(new long[]{0, src});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        long d = top[0]; int u = (int) top[1];
        if (d > dist[u]) continue;                 // stale entry, skip
        for (int[] e : graph.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {           // relaxation
                dist[v] = dist[u] + w;
                pq.add(new long[]{dist[v], v});
            }
        }
    }
    return dist;
}

// graph[u] = array of [neighbor, weight]; uses a small binary min-heap
function dijkstra(graph, src) {
  const n = graph.length;
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const heap = [[0, src]];                          // [distance, vertex]
  const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };
  const push = (item) => {
    heap.push(item); let i = heap.length - 1;
    while (i > 0) { const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break; swap(i, p); i = p; }
  };
  const pop = () => {
    const top = heap[0], last = heap.pop();
    if (heap.length) { heap[0] = last; let i = 0;
      while (true) { let s = i, l = 2*i+1, r = 2*i+2;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break; swap(i, s); i = s; } }
    return top;
  };
  while (heap.length) {
    const [d, u] = pop();
    if (d > dist[u]) continue;                      // stale entry, skip
    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {                  // relaxation
        dist[v] = dist[u] + w;
        push([dist[v], v]);
      }
    }
  }
  return dist;
}

import heapq

# graph[u] = list of (neighbor, weight)
def dijkstra(graph, src):
    n = len(graph)
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]                                 # (distance, vertex)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:                             # stale entry, skip
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:               # relaxation
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

Pitfall: The if (d > dist[u]) continue; “stale check” is essential. Lazy-deletion heaps keep outdated entries; without skipping them you re-process vertices and the running time degrades. Equally important: Dijkstra is wrong with negative edges — a later cheaper path can appear after a vertex is settled. For negative weights use Bellman-Ford.

Reconstructing the path

Keep a parent array; whenever you relax u → v, set parent[v] = u. Then walk parent back from the target to the source and reverse it.

Complexity

Time: O((V + E) log V) with a binary heap.
Space: O(V + E) for the graph plus O(V) for distances and the heap.

When to use Dijkstra

Use it for single-source shortest paths on graphs with non-negative weights — road networks, latency-weighted routing, game pathfinding. Need negative weights or negative-cycle detection? See Bellman-Ford. Need all pairs at once on a small graph? See Floyd-Warshall.