JAVA-205 · Lesson 9 of 12 · 24 min

Shortest paths

▶ Video coming soon A video version of this lesson is on the way.

Last week's breadth-first search found the route with the fewest stops. But the volunteers on the cargo bike care about minutes, not stops, and the fewest-stop route from the shop to Dundas took 49 minutes when a four-road route took 45. On Tuesday, November 16, 2027, Ingrid introduces the algorithm inside every route planner and network router: Dijkstra's algorithm for the shortest path in a weighted graph. By the end of the evening Hamza can print, for every partner site, the quickest route from the shop and its riding time.

The shortest-path problem

In a weighted graph the length of a path is the sum of its edge weights, and a shortest path between two vertices is one with the smallest length. The single-source shortest-path problem asks for the shortest path from one start vertex to every other vertex. For an unweighted graph, or one where every edge has the same weight, BFS solves it. When weights differ, BFS can be fooled, because a path with more edges can be shorter, so we need a method that explores vertices in order of distance, not in order of edge count.

Dijkstra's idea

Edsger Dijkstra published the algorithm in 1959. It keeps a tentative distance for every vertex, starting at 0 for the start and infinity for the rest. Repeatedly, it picks the unfinished vertex with the smallest tentative distance and declares that distance final. Then it relaxes each edge leaving that vertex: if going through it gives a shorter route to a neighbour than the neighbour's tentative distance, the tentative distance is lowered. When every reachable vertex is finished, the tentative distances are the true shortest distances.

Why is the smallest tentative distance safe to declare final? Any other route to that vertex would have to leave the finished region through some other unfinished vertex, which is already at least as far away, and then add more edges, which can only make it longer because the weights are not negative. That last condition, no negative weights, is essential, and we return to it at the end of the lesson.

Dijkstra with a priority queue

Picking the vertex with the smallest tentative distance is exactly what a priority queue does, and JAVA-201's PriorityQueue is a binary heap with O(log n) insertion and removal. The usual Java version adds a new entry to the queue every time a distance improves, instead of updating the old entry, and simply skips an entry when it is taken out for a vertex that is already finished. This is called lazy deletion, and it keeps the code short.

Java Example · Main.java
import java.util.*;

public class Main {
    record Edge(String to, int minutes) {}

    static Map<String, List<Edge>> graph() {
        Object[][] roads = {{"Shop", "Corktown", 9}, {"Shop", "Crown Point", 11}, {"Corktown", "Crown Point", 7}, {"Corktown", "Kirkendall", 12},
                {"Shop", "Kirkendall", 23}, {"Kirkendall", "Westdale", 10}, {"Westdale", "Dundas", 14}, {"Kirkendall", "Dundas", 26},
                {"Crown Point", "Stoney Creek", 18}, {"Shop", "Stoney Creek", 31}};
        Map<String, List<Edge>> g = new LinkedHashMap<>();
        for (Object[] r : roads) {
            String a = (String) r[0], b = (String) r[1];
            int m = (Integer) r[2];
            g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Edge(b, m));
            g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Edge(a, m));
        }
        return g;
    }

    record Step(String place, int dist) {}

    static Map<String, Integer> dijkstra(Map<String, List<Edge>> g, String from, Map<String, String> parent) {
        Map<String, Integer> dist = new LinkedHashMap<>();
        Set<String> done = new HashSet<>();
        PriorityQueue<Step> pq = new PriorityQueue<>(Comparator.comparingInt(Step::dist).thenComparing(Step::place));
        dist.put(from, 0);
        pq.add(new Step(from, 0));
        while (!pq.isEmpty()) {
            Step s = pq.poll();
            if (!done.add(s.place())) continue;
            for (Edge e : g.get(s.place())) {
                int d = s.dist() + e.minutes();
                if (d < dist.getOrDefault(e.to(), Integer.MAX_VALUE)) {
                    dist.put(e.to(), d);
                    parent.put(e.to(), s.place());
                    pq.add(new Step(e.to(), d));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> dist = dijkstra(graph(), "Shop", parent);
        dist.forEach((place, d) -> System.out.println(place + ": " + d + " min"));
    }
}
Output
Shop: 0 min
Corktown: 9 min
Crown Point: 11 min
Kirkendall: 21 min
Stoney Creek: 29 min
Westdale: 31 min
Dundas: 45 min

What this code does

Each Step pairs a place with a distance, and the priority queue always hands back the step with the smallest distance, breaking ties by name so the run is repeatable. A step for a place that is already done is skipped, which is the lazy deletion. From the Shop, Dundas is 45 minutes away and Stoney Creek is 29, both quicker than their direct or fewest-stop routes.

Two results are worth checking against the map. The Shop has a direct road to Stoney Creek of 31 minutes, but the route through Crown Point takes 11 + 18 = 29, so Dijkstra prefers it. And the route to Kirkendall through Corktown, 9 + 12 = 21 minutes, beats the direct road of 23. A shortest path is often not the most obvious one.

Watching it work

Printing the order in which vertices are finished shows the algorithm's defining property: vertices are settled in increasing order of distance, like BFS rings but measured in minutes instead of edges.

Java Example · Main.java
import java.util.*;

public class Main {
    record Edge(String to, int minutes) {}

    static Map<String, List<Edge>> graph() {
        Object[][] roads = {{"Shop", "Corktown", 9}, {"Shop", "Crown Point", 11}, {"Corktown", "Crown Point", 7}, {"Corktown", "Kirkendall", 12},
                {"Shop", "Kirkendall", 23}, {"Kirkendall", "Westdale", 10}, {"Westdale", "Dundas", 14}, {"Kirkendall", "Dundas", 26},
                {"Crown Point", "Stoney Creek", 18}, {"Shop", "Stoney Creek", 31}};
        Map<String, List<Edge>> g = new LinkedHashMap<>();
        for (Object[] r : roads) {
            String a = (String) r[0], b = (String) r[1];
            int m = (Integer) r[2];
            g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Edge(b, m));
            g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Edge(a, m));
        }
        return g;
    }

    record Step(String place, int dist) {}

    public static void main(String[] args) {
        Map<String, List<Edge>> g = graph();
        Map<String, Integer> dist = new HashMap<>(Map.of("Shop", 0));
        Set<String> done = new HashSet<>();
        PriorityQueue<Step> pq = new PriorityQueue<>(Comparator.comparingInt(Step::dist).thenComparing(Step::place));
        pq.add(new Step("Shop", 0));
        int pushes = 1, skipped = 0;
        while (!pq.isEmpty()) {
            Step s = pq.poll();
            if (!done.add(s.place())) { skipped++; continue; }
            System.out.println("settle " + s.place() + " at " + s.dist());
            for (Edge e : g.get(s.place())) {
                int d = s.dist() + e.minutes();
                if (d < dist.getOrDefault(e.to(), Integer.MAX_VALUE)) {
                    System.out.println("   improve " + e.to() + " to " + d);
                    dist.put(e.to(), d);
                    pq.add(new Step(e.to(), d));
                    pushes++;
                }
            }
        }
        System.out.println(pushes + " entries added to the queue, " + skipped + " stale entries skipped");
    }
}
Output
settle Shop at 0
   improve Corktown to 9
   improve Crown Point to 11
   improve Kirkendall to 23
   improve Stoney Creek to 31
settle Corktown at 9
   improve Kirkendall to 21
settle Crown Point at 11
   improve Stoney Creek to 29
settle Kirkendall at 21
   improve Westdale to 31
   improve Dundas to 47
settle Stoney Creek at 29
settle Westdale at 31
   improve Dundas to 45
settle Dundas at 45
10 entries added to the queue, 3 stale entries skipped

What this code does

The trace shows each settled place and every improvement it makes to a neighbour's tentative distance. Kirkendall is first given 23 by the direct road and then improved to 21 through Corktown, so its old entry becomes stale and is skipped later. Places are settled at 0, 9, 11, 21, 29, 31 and 45 minutes, always in increasing order.

A table with one column per place and one row per step of the algorithm. Row 1 after settling the Shop at 0: Corktown 9, Crown Point 11, Kirkendall 23, Stoney Creek 31, others infinity. Row 2 after settling Corktown: Kirkendall improves to 21. Row 3 after Crown Point: Stoney Creek improves to 29. Later rows show Westdale 31 and Dundas 45. Each settled value is circled in the row where it becomes final.
Tentative distances from the Shop shrink until each place is settled in increasing order

Rebuilding the route

As with BFS, recording the parent of each vertex whenever its distance improves lets you rebuild the actual route afterwards. The parent links of the finished vertices form a shortest-path tree rooted at the start: following them back from any vertex gives a shortest route to it.

Java Example · Main.java
import java.util.*;

public class Main {
    record Edge(String to, int minutes) {}

    static Map<String, List<Edge>> graph() {
        Object[][] roads = {{"Shop", "Corktown", 9}, {"Shop", "Crown Point", 11}, {"Corktown", "Crown Point", 7}, {"Corktown", "Kirkendall", 12},
                {"Shop", "Kirkendall", 23}, {"Kirkendall", "Westdale", 10}, {"Westdale", "Dundas", 14}, {"Kirkendall", "Dundas", 26},
                {"Crown Point", "Stoney Creek", 18}, {"Shop", "Stoney Creek", 31}};
        Map<String, List<Edge>> g = new LinkedHashMap<>();
        for (Object[] r : roads) {
            String a = (String) r[0], b = (String) r[1];
            int m = (Integer) r[2];
            g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Edge(b, m));
            g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Edge(a, m));
        }
        return g;
    }

    record Step(String place, int dist) {}

    static Map<String, Integer> dijkstra(Map<String, List<Edge>> g, String from, Map<String, String> parent) {
        Map<String, Integer> dist = new LinkedHashMap<>();
        Set<String> done = new HashSet<>();
        PriorityQueue<Step> pq = new PriorityQueue<>(Comparator.comparingInt(Step::dist).thenComparing(Step::place));
        dist.put(from, 0);
        pq.add(new Step(from, 0));
        while (!pq.isEmpty()) {
            Step s = pq.poll();
            if (!done.add(s.place())) continue;
            for (Edge e : g.get(s.place())) {
                int d = s.dist() + e.minutes();
                if (d < dist.getOrDefault(e.to(), Integer.MAX_VALUE)) {
                    dist.put(e.to(), d);
                    parent.put(e.to(), s.place());
                    pq.add(new Step(e.to(), d));
                }
            }
        }
        return dist;
    }

    static List<String> route(Map<String, String> parent, String from, String to) {
        LinkedList<String> path = new LinkedList<>();
        for (String p = to; p != null; p = p.equals(from) ? null : parent.get(p)) path.addFirst(p);
        return path;
    }

    public static void main(String[] args) {
        Map<String, String> parent = new HashMap<>();
        Map<String, Integer> dist = dijkstra(graph(), "Shop", parent);
        for (String to : List.of("Dundas", "Stoney Creek", "Kirkendall")) {
            System.out.println(String.join(" -> ", route(parent, "Shop", to)) + "  (" + dist.get(to) + " min)");
        }
    }
}
Output
Shop -> Corktown -> Kirkendall -> Westdale -> Dundas  (45 min)
Shop -> Crown Point -> Stoney Creek  (29 min)
Shop -> Corktown -> Kirkendall  (21 min)

What this code does

The parent map is filled in whenever a shorter route to a place is found, so at the end it holds the last and best improvement. route walks back from the destination to the Shop and builds the list from the front. The quickest route to Dundas uses four roads through Corktown, Kirkendall and Westdale.

How fast is it?

Each vertex is settled once and each edge is relaxed once from each end. Every relaxation that improves a distance adds an entry to the priority queue, at O(log E) each, and every entry is removed once. So Dijkstra with a binary heap runs in O((V + E) log V) time, usually written O(E log V) for connected graphs. For the 7-place pickup map that is trivial; for a city road network with a million intersections it is still fast enough to answer in well under a second, and real route planners add further tricks on top.

Shortest-path algorithms
GraphAlgorithmTime
Unweighted, or all weights equalBreadth-first searchO(V + E)
Non-negative weightsDijkstra with a binary heapO((V + E) log V)
Some negative weights, no negative cyclesBellman-FordO(V × E)
Directed acyclic graphRelax edges in topological orderO(V + E)
Every pair of vertices, small graphFloyd-WarshallO(V³)

Negative weights

Riding times are never negative, but some weights can be. Suppose an edge's weight is the net cost of a trip, and one trip earns more than it costs because a business pays the shop to pick up its old bikes. Dijkstra can then give wrong answers: it may finalize a vertex before discovering that a longer-looking path with a negative edge is actually shorter. The Bellman-Ford algorithm handles negative weights by relaxing every edge V − 1 times, and a further pass that still improves something reveals a negative cycle, a loop whose total is negative, around which no shortest path exists.

Java Example · Main.java
import java.util.*;

public class Main {
    record Arc(int from, int to, int cost) {}

    public static void main(String[] args) {
        String[] names = {"A", "B", "C"};
        List<Arc> arcs = List.of(new Arc(0, 1, 4), new Arc(0, 2, 5), new Arc(2, 1, -3));

        int[] dist = new int[3];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        for (int round = 1; round < names.length; round++) {
            for (Arc a : arcs) {
                if (dist[a.from()] != Integer.MAX_VALUE && dist[a.from()] + a.cost() < dist[a.to()]) {
                    dist[a.to()] = dist[a.from()] + a.cost();
                }
            }
        }
        for (int i = 0; i < names.length; i++) System.out.println(names[i] + ": " + dist[i]);
        System.out.println("Dijkstra would settle B at 4 before it sees the route A -> C -> B = " + (5 - 3));
    }
}
Output
A: 0
B: 2
C: 5
Dijkstra would settle B at 4 before it sees the route A -> C -> B = 2

What this code does

In this small directed graph the route from A to B through C costs 5 minus 3, which is 2, cheaper than the direct arc of 4. Bellman-Ford relaxes every arc in each of V minus 1 rounds and finds the 2. Dijkstra would settle B at 4 first, because 4 is smaller than C's 5, and never revisit it.

In practice, use Dijkstra when weights are distances, times or prices that cannot be negative, which covers almost every routing problem, and reach for Bellman-Ford only when a negative weight is genuinely part of the model.

Try it yourself

Complete the relaxation

The starter's Dijkstra settles places but never improves their distances. Add the relaxation step: for each edge from the settled place, if the route through it is shorter than the neighbour's current distance, update the distance and add a new Step to the queue.

The program should print {Shop=0, Corktown=9, Crown Point=11, Kirkendall=21, Stoney Creek=29, Westdale=31, Dundas=45}.

import java.util.*;

public class Main {
    record Edge(String to, int minutes) {}

    static Map<String, List<Edge>> graph() {
        Object[][] roads = {{"Shop", "Corktown", 9}, {"Shop", "Crown Point", 11}, {"Corktown", "Crown Point", 7}, {"Corktown", "Kirkendall", 12},
                {"Shop", "Kirkendall", 23}, {"Kirkendall", "Westdale", 10}, {"Westdale", "Dundas", 14}, {"Kirkendall", "Dundas", 26},
                {"Crown Point", "Stoney Creek", 18}, {"Shop", "Stoney Creek", 31}};
        Map<String, List<Edge>> g = new LinkedHashMap<>();
        for (Object[] r : roads) {
            String a = (String) r[0], b = (String) r[1];
            int m = (Integer) r[2];
            g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Edge(b, m));
            g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Edge(a, m));
        }
        return g;
    }

    record Step(String place, int dist) {}

    public static void main(String[] args) {
        Map<String, List<Edge>> g = graph();
        Map<String, Integer> dist = new HashMap<>(Map.of("Shop", 0));
        Map<String, Integer> settled = new LinkedHashMap<>();
        PriorityQueue<Step> pq = new PriorityQueue<>(Comparator.comparingInt(Step::dist).thenComparing(Step::place));
        pq.add(new Step("Shop", 0));
        while (!pq.isEmpty()) {
            Step s = pq.poll();
            if (settled.containsKey(s.place())) continue;
            settled.put(s.place(), s.dist());
        }
        System.out.println(settled);
    }
}

Try it yourself

How long is this route?

Kofi has written down a route by hand. Complete length(Map<String, List<Edge>> g, List<String> route) so it adds up the minutes of each road between consecutive places, and returns -1 if two consecutive places have no road between them.

The program should print 45, 49 and -1, one per line.

import java.util.*;

public class Main {
    record Edge(String to, int minutes) {}

    static Map<String, List<Edge>> graph() {
        Object[][] roads = {{"Shop", "Corktown", 9}, {"Shop", "Crown Point", 11}, {"Corktown", "Crown Point", 7}, {"Corktown", "Kirkendall", 12},
                {"Shop", "Kirkendall", 23}, {"Kirkendall", "Westdale", 10}, {"Westdale", "Dundas", 14}, {"Kirkendall", "Dundas", 26},
                {"Crown Point", "Stoney Creek", 18}, {"Shop", "Stoney Creek", 31}};
        Map<String, List<Edge>> g = new LinkedHashMap<>();
        for (Object[] r : roads) {
            String a = (String) r[0], b = (String) r[1];
            int m = (Integer) r[2];
            g.computeIfAbsent(a, k -> new ArrayList<>()).add(new Edge(b, m));
            g.computeIfAbsent(b, k -> new ArrayList<>()).add(new Edge(a, m));
        }
        return g;
    }

    static int length(Map<String, List<Edge>> g, List<String> route) {
        return route.size();
    }

    public static void main(String[] args) {
        Map<String, List<Edge>> g = graph();
        System.out.println(length(g, List.of("Shop", "Corktown", "Kirkendall", "Westdale", "Dundas")));
        System.out.println(length(g, List.of("Shop", "Kirkendall", "Dundas")));
        System.out.println(length(g, List.of("Shop", "Dundas")));
    }
}

Common mistakes

  • MistakeUsing breadth-first search for a weighted graph.

    InsteadBFS counts edges; use Dijkstra when edges have different weights.

  • MistakeRunning Dijkstra on a graph with negative weights.

    InsteadUse Bellman-Ford, which also detects negative cycles.

  • MistakeSettling a vertex again when a stale queue entry comes out.

    InsteadSkip entries for vertices that are already finished.

  • MistakeAdding the edge weight to Integer.MAX_VALUE for an unreached vertex.

    InsteadOnly relax from vertices with a real distance, or the sum overflows.

  • MistakeForgetting to record parents.

    InsteadStore the parent whenever a distance improves, so the route can be rebuilt.

Summary and key terms

  • The length of a path in a weighted graph is the sum of its edge weights, and the single-source shortest-path problem asks for the shortest path from one vertex to all others.
  • Dijkstra's algorithm repeatedly settles the unfinished vertex with the smallest tentative distance and relaxes its edges, lowering neighbours' distances when a shorter route is found; vertices are settled in increasing order of distance.
  • With a PriorityQueue and lazy deletion of stale entries it runs in O((V + E) log V).
  • Recording parents gives a shortest-path tree from which routes are rebuilt.
  • Dijkstra requires non-negative weights; Bellman-Ford handles negative weights in O(V × E) and detects negative cycles, and BFS remains the right tool when every edge has the same weight.
Path length
The sum of the weights of a path's edges.
Shortest path
A path between two vertices with the smallest possible length.
Single-source shortest paths
The shortest paths from one start vertex to every other vertex.
Dijkstra's algorithm
A shortest-path algorithm for graphs with non-negative weights that settles vertices in order of distance.
Tentative distance
The best distance to a vertex found so far, which may still improve.
Relaxation
Checking whether a route through one more edge is shorter, and updating the distance if it is.
Lazy deletion
Leaving outdated entries in a priority queue and skipping them when they come out.
Shortest-path tree
The tree formed by the parent links of the shortest paths from a start vertex.
Bellman-Ford algorithm
A slower shortest-path algorithm that allows negative weights.
Negative cycle
A cycle whose edge weights add up to less than zero.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. What is the shortest riding time from the Shop to Stoney Creek, and why is it not the direct road?

    Show answer

    29 minutes through Crown Point; the direct road takes 31.

  2. In what order does Dijkstra's algorithm settle vertices?

    Show answer

    In increasing order of their shortest distance from the start.

  3. What is a stale entry in the priority queue?

    Show answer

    An older, larger distance for a vertex whose distance has since improved.

  4. Why can't Dijkstra handle negative weights?

    Show answer

    It may settle a vertex before finding a cheaper route that uses a negative edge.

  5. What is Dijkstra's running time with a binary heap?

    Show answer

    O((V + E) log V).

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz