Shortest Path (Dijkstra)

BFS finds the shortest path in an unweighted graph because every edge "costs" the same one step. The moment edges have different weights — flight durations, road distances, network latencies — BFS breaks: a path with more edges can still be cheaper overall than a path with fewer, heavier ones. Dijkstra's algorithm solves shortest path for weighted graphs (as long as no edge weight is negative) by always expanding the closest unvisited node next, using a min-heap to efficiently find that node.

The Problem BFS Can't Solve

A --1-- B
|       |
10      1
|       |
C ------D
   1

BFS from A would report B and C as equally "close" (both one edge away) and never realize that A→B→D→C (cost 1+1+1=3) is far cheaper than A→C directly (cost 10). BFS counts edges, not weights — it has no concept of "cost" at all.

Dijkstra's Algorithm

Keep a dist[] array initialized to infinity (0 for the source). Use a min-heap (Java's PriorityQueue) of (node, distance) pairs, always pulling out the node with the smallest known distance next. For each of its neighbors, if going through the current node gives a shorter path than what's currently recorded, update it — this update step is called relaxation.

class Edge {
    int to, weight;
    Edge(int to, int weight) { this.to = to; this.weight = weight; }
}

int[] dijkstra(List<List<Edge>> adj, int source, int V) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    // min-heap ordered by distance: smallest known distance comes out first
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.add(new int[]{source, 0});  // {node, distance}

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int node = curr[0], d = curr[1];

        if (d > dist[node]) continue;  // stale entry, a shorter path was already found

        for (Edge edge : adj.get(node)) {
            int newDist = d + edge.weight;
            if (newDist < dist[edge.to]) {
                dist[edge.to] = newDist;                       // relax: found a shorter path
                pq.add(new int[]{edge.to, newDist});
            }
        }
    }
    return dist;
}

Trace-Through on the Example Graph

Using A=0, B=1, C=2, D=3 and edges A-B(1), A-C(10), B-D(1), C-D(1), starting from A:

Initial:        dist = [A:0, B:inf, C:inf, D:inf]     heap: [(A,0)]

Pop (A,0):      relax B: 0+1=1  < inf -> dist[B]=1     heap: [(B,1), (C,10)]
                relax C: 0+10=10 < inf -> dist[C]=10
dist = [A:0, B:1, C:10, D:inf]

Pop (B,1):      relax D: 1+1=2  < inf -> dist[D]=2     heap: [(D,2), (C,10)]
dist = [A:0, B:1, C:10, D:2]

Pop (D,2):      relax C: 2+1=3  < 10 -> dist[C]=3      heap: [(C,3), (C,10)]
dist = [A:0, B:1, C:3, D:2]

Pop (C,3):      no shorter path found through C        heap: [(C,10)]
dist = [A:0, B:1, C:3, D:2]

Pop (C,10):     10 > dist[C]=3 -> stale entry, skipped  heap: []

Final shortest distances from A:  B=1, C=3, D=2

Notice C's shortest distance ends up as 3 (via A→B→D→C), not 10 (the direct A→C edge) — exactly the case a plain BFS-by-edge-count would have missed.

Time complexity: O((V + E) log V) — each of the up to E edge relaxations does a heap insert/removal costing O(log V), and every vertex is popped from the heap at least once. Space complexity: O(V + E) for the adjacency list plus O(V) for the distance array and heap contents.

The Key Limitation: Negative Weights

For graphs that may contain negative edge weights (but no negative cycles), Bellman-Ford is the standard alternative — it relaxes every edge V-1 times instead of relying on a heap's greedy ordering, which correctly handles negative weights at the cost of a slower O(V·E) runtime. It's not covered in depth here since Dijkstra covers the overwhelming majority of interview shortest-path questions, but it's worth knowing the name and the trade-off it exists for.