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.
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"));
}
}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.
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");
}
}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.
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.
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)");
}
}
}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.
| Graph | Algorithm | Time |
|---|---|---|
| Unweighted, or all weights equal | Breadth-first search | O(V + E) |
| Non-negative weights | Dijkstra with a binary heap | O((V + E) log V) |
| Some negative weights, no negative cycles | Bellman-Ford | O(V × E) |
| Directed acyclic graph | Relax edges in topological order | O(V + E) |
| Every pair of vertices, small graph | Floyd-Warshall | O(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.
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));
}
}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.
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.
In what order does Dijkstra's algorithm settle vertices?
Show answer
In increasing order of their shortest distance from the start.
What is a stale entry in the priority queue?
Show answer
An older, larger distance for a vertex whose distance has since improved.
Why can't Dijkstra handle negative weights?
Show answer
It may settle a vertex before finding a cheaper route that uses a negative edge.
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.
Create a free account to save your progress, take quizzes and earn a certificate.