Dijkstra algo

The problem, simply

You get a map of V places joined by two-way roads. Every road has a cost, like minutes of walking, and no cost is below zero. You also get a starting place, src.

For every place, give back the smallest total cost to get there from src. If a place cannot be reached, its answer stays "infinity".

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a list of costs. In every round, scan all places to find the cheapest one that is not settled yet. Settle it, then try every road out of it.

1. Set every cost to infinity, and the cost of src to 0.
2. Repeat V times: scan all places and pick the unsettled one with the smallest cost.
3. Mark it settled. For each road to a neighbor, if cost[u] + w is smaller than the neighbor's cost, write the smaller number.

class DijkstraArray {
    public static int[] dijkstra(int V, int[][] edges, int src) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});   // two-way road
        }

        int[] dist = new int[V];
        boolean[] settled = new boolean[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        for (int round = 0; round < V; round++) {
            int u = -1;
            for (int v = 0; v < V; v++) {                // scan everyone for the cheapest
                if (!settled[v] && (u == -1 || dist[v] < dist[u])) u = v;
            }
            if (dist[u] == Integer.MAX_VALUE) break;    // the rest cannot be reached
            settled[u] = true;
            for (int[] nb : adj.get(u)) {
                int v = nb[0], w = nb[1];
                if (!settled[v] && dist[u] + w < dist[v]) dist[v] = dist[u] + w;
            }
        }
        return dist;
    }
}

How long it takes: V rounds, and each round scans all V places, O(V^2). The roads add O(E) on top. Extra room: two arrays, O(V). On a very crowded map, where E is close to V^2, this is actually the best choice.

Way 2: the clever way

The slow part is the scan for the cheapest place. A min-heap, which is the pile of sticky notes, hands you the smallest note in O(log V) instead.

1. Push the note 0:src, meaning cost 0 at place src. In the pictures a note 3:1 means "place 1 for cost 3".
2. Pop the smallest note d:u. If d is bigger than the best cost we already wrote for u, the note is old. Throw it away.
3. Otherwise u is settled. For each road u to v with cost w, if d + w beats dist[v], write it and push a new note d + w : v.
4. Stop when the pile is empty.

class DijkstraHeap {
    public static int[] dijkstra(int V, int[][] edges, int src) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});
        }

        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        // each note is {cost, place}; the smallest cost comes out first
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.add(new int[]{0, src});

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;                   // an old note, throw it away
            for (int[] nb : adj.get(u)) {
                int v = nb[0], w = nb[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    pq.add(new int[]{dist[v], v});       // a new, better note
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3}};
        System.out.println(Arrays.toString(dijkstra(5, edges, 0)));  // [0, 3, 1, 4, 7]
    }
}

How long it takes: every road can push at most one note, so the heap sees at most E notes, and each push or pop costs O(log E), which is O(log V). In total O((V + E) log V). Extra room: the road lists plus the heap, O(V + E).

Watch out for

• Forgetting the old-note check if (d > dist[u]) continue. The answer stays right, but you redo work and can slow down badly on big graphs.
• Writing the comparator as a[0] - b[0] overflows when costs are near Integer.MAX_VALUE. Use Integer.compare, or long costs.
• Adding dist[u] + w when dist[u] is still Integer.MAX_VALUE wraps to a negative number. The heap version never pops an unreached place, but the array version must check first.
• One-way roads: add only adj.get(u).add(...), not both directions.

What interviewers ask next

• How do you print the actual route? Keep parent[v] = u every time you improve v. Walk the parents back from the target and reverse.
• Only one target? Stop as soon as you pop the target. Its cost is final at that moment.
• What if every road costs 0 or 1? Use 0-1 BFS with a deque: push 0-cost neighbors to the front and 1-cost neighbors to the back. It runs in O(V + E).
• Why does it fail with negative edges, but is fine with zero edges? Zero never makes a later note smaller than a settled one; a negative edge can.
• What about a limit on the number of roads used? Then the cheapest cost alone is not enough to settle a place. See "Cheapest flights within K stops".

Remember this

Grown-up words: places are vertices, roads are weighted edges, the pile of sticky notes is a priority queue (a min-heap), writing a better cost is relaxing an edge, throwing away old notes is lazy deletion, and the highlighted roads at the end form the shortest path tree.