Dijkstra

Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a graph with non-negative edge weights. It uses a min-heap (priority queue) to always expand the node with the smallest known distance.

When to Use

  • Single-source shortest path in a weighted graph (directed or undirected).
  • All edge weights must be non-negative. If you have negative edges, use Bellman–Ford instead.
  • Typical problems: network delay, cheapest flight with at most K stops, path with minimum max-edge, etc.

Core Idea

  1. Keep dist[v] = best known distance from source to v. Initially dist[source] = 0, others +∞.
  2. Use a min-heap (priority queue) keyed by distance. Start with (0, source).
  3. Repeatedly poll the node u with smallest distance. For each neighbor v with weight w:
    • If dist[u] + w < dist[v], update dist[v] and offer (dist[v], v).
  4. Once a node is polled, its distance is final (true for non-negative weights).

Java Implementation

Java
// Adjacency list: adj.get(u) = list of {neighbor, weight}
int[] dijkstra(List<List<int[]>> adj, int source) {
    int n = adj.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    // min-heap: (distance, node)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, source});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d != dist[u]) continue; // stale entry, skip

        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            int newDist = dist[u] + w;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.offer(new int[]{newDist, v});
            }
        }
    }
    return dist;
}

The if (d != dist[u]) continue check skips stale entries: the same node can be pushed multiple times with improving distances; we only process when the popped value is still the current best.

Time Complexity

  • Time: O((V + E) log V) with a binary heap (each edge may cause one push, and we do at most O(E) pushes and V polls).
  • Space: O(V) for dist and the heap.

Single Target

To stop as soon as you reach a target node t, break out of the loop when u == t after polling. The rest of the algorithm stays the same.

Summary

Use Dijkstra for single-source shortest path with non-negative weights. Maintain a min-heap of (distance, node), relax edges when you get a shorter path, and skip stale heap entries. For unweighted graphs, BFS is simpler and sufficient.