Dijkstra's Algorithm

How It Works

Dijkstra's algorithm finds shortest paths from a source in a graph with non-negative edge weights. It maintains a min-heap of (distance, node) pairs and repeatedly extracts the closest unsettled node. Because all weights are non-negative, the first time a node is extracted its distance is final — no shorter route can appear later. Each extraction relaxes the node's outgoing edges, pushing improved distances onto the heap.

With a binary heap the running time is O(E log V): every edge can trigger at most one improvement push, and every push or pop costs O(log V). Stale heap entries are skipped by comparing against the current best distance on extraction, which keeps the implementation simple without a decrease-key operation.

Step-by-Step Visualization

Code

static int[] dijkstra(List<int[]>[] graph, int start) {
  int[] dist = new int[graph.length];
  Arrays.fill(dist, Integer.MAX_VALUE);
  dist[start] = 0;
  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
  pq.add(new int[]{0, start}); // [distance, node]

  while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int d = curr[0], u = curr[1];
    if (d > dist[u]) continue;

    for (int[] edge : graph[u]) {
      int v = edge[0], w = edge[1];
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.add(new int[]{dist[v], v});
      }
    }
  }
  return dist;
}

Tips & Gotchas

Practice Problems

• 1Network Delay Time
• 2Path With Minimum Effort
• 3Cheapest Flights Within K Stops
• 4Swim in Rising Water

About the Shortest Path Pattern

Find the minimum cost path between nodes. The right algorithm depends on the graph: unweighted → BFS, non-negative weights → Dijkstra, negative weights → Bellman-Ford, all-pairs → Floyd-Warshall.

Common Graphs Interview Problems

• Number of Islands
• Clone Graph
• Course Schedule
• Pacific Atlantic Water Flow
• Network Delay Time
• Minimum Spanning Tree
• Word Ladder

Frequently Asked Questions

Other Shortest Path Techniques