Dijkstra: The Shortest Route

When edges have lengths

BFS counts hops. But on a real map one road might be 2 km and another 50 km. For the shortest total distance we use Dijkstra's algorithm (all lengths must be zero or positive).

The idea

1. Every place starts with distance “infinity”, except the start: 0.
2. Pick the unfinished place with the smallest known distance – a PriorityQueue does this fast.
3. Its distance is now final. Try every road out of it: if going through it makes a neighbour closer, update the neighbour and add it to the queue.
4. Repeat until the queue is empty.

Think of it like this: Water spreading from a tap through pipes of different lengths: it reaches nearby joints first, and each joint is reached for the first time along the shortest pipe route.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class ByDistance implements Comparator<long[]> {
    public int compare(long[] a, long[] b) { return Long.compare(a[1], b[1]); }
}

public class Main {
    public static void main(String[] args) {
        int n = 5;
        ArrayList<ArrayList<int[]>> g = new ArrayList<ArrayList<int[]>>();   // {neighbour, length}
        for (int i = 0; i <= n; i++) g.add(new ArrayList<int[]>());
        int[][] roads = {{1, 2, 4}, {1, 3, 1}, {3, 2, 2}, {2, 4, 5}, {3, 4, 8}, {4, 5, 3}};
        for (int[] r : roads) {
            g.get(r[0]).add(new int[]{r[1], r[2]});
            g.get(r[1]).add(new int[]{r[0], r[2]});
        }

        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<long[]>(new ByDistance());   // {place, distance}
        pq.offer(new long[]{1, 0});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            int u = (int) top[0];
            if (top[1] > dist[u]) continue;           // an old, out-of-date entry: skip
            for (int[] road : g.get(u)) {
                int v = road[0];
                if (dist[u] + road[1] < dist[v]) {     // found a shorter way to v
                    dist[v] = dist[u] + road[1];
                    pq.offer(new long[]{v, dist[v]});
                }
            }
        }
        for (int place = 1; place <= n; place++) System.out.println("to " + place + ": " + dist[place] + " km");
    }
}

Output

to 1: 0 km
to 2: 3 km
to 3: 1 km
to 4: 8 km
to 5: 11 km

Notice place 2: the direct road is 4 km, but going 1 → 3 → 2 is only 3 km, and Dijkstra finds it. With a PriorityQueue the running time is O((n + m) log n).

Common mistake: Using Dijkstra with negative road lengths. It assumes a place is final once it's the closest – a negative road could make it closer later. (Other algorithms, like Bellman-Ford, handle that.)