Core invariant

At each step, pull vertex with smallest tentative distance. Its distance is now final — no shorter path can exist (relies on non-negative weights).

Advertisement

Implementation

int[] dijkstra(int src, List[] graph) {
  int[] dist = new int[graph.length];
  Arrays.fill(dist, Integer.MAX_VALUE);
  dist[src] = 0;
  PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
  pq.offer(new int[]{0, src});
  while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int d = cur[0], u = cur[1];
    if (d > dist[u]) continue; // stale entry
    for (int[] edge : graph[u]) {
      int v = edge[0], w = edge[1];
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.offer(new int[]{dist[v], v});
      }
    }
  }
  return dist;
}
Advertisement

Why non-negative weights

With negative weights, a later relaxation could improve a 'finalized' distance. Use Bellman-Ford instead.

Complexity variants

Binary heap: O((V+E) log V). Fibonacci heap: O(E + V log V). Array-based (dense): O(V²).