The Fastest Drive, Not the Fewest Roads: Dijkstra's Algorithm

Find the fastest route through a town where every road takes a different number of minutes: why counting roads, always taking the shortest next road and trying every route all fail, and the algorithm a GPS uses instead, Dijkstra's algorithm, made fast by a priority queue.

Freelancer · Data Structures · Updated

By

After this lesson you can

  • Trace Dijkstra's algorithm as it settles the closest place first
  • Explain when a route needs Dijkstra's algorithm instead of breadth-first search

Key takeaways

  • When edges have weights, the route with the fewest edges isn't always the shortest, and always taking the shortest next road can miss the fastest route too.
  • Dijkstra's algorithm settles the closest place not yet settled, again and again: once a place is settled, its time is final.
  • A priority queue hands back the closest place waiting, so each step is quick.
  • It needs weights of zero or more, and it takes O((V + E) log V) time with a priority queue.
  • Use breadth-first search when every edge counts the same, and Dijkstra's algorithm when edges have different costs.

Before this: How Many Steps Apart? Breadth-First Search finds the fewest edges. It counts every road as one step, however long the road is.

A small town wants a route planner in its map app: type where you're going, and it shows the fastest way from Home, with the minutes. The town has five places and six two-way roads, each with the minutes it takes to drive, so it's a weighted graph (Who Knows Whom? When Anything Can Connect: Graphs):

Road Minutes
Home to Market 4
Home to Bridge 2
Bridge to Market 1
Market to School 5
Bridge to Stadium 8
School to Stadium 3

Delivery apps plan drivers' stops the same way, and games move characters around slow ground. What's the fastest drive from Home to each place?

What would you try?

Breadth-first search, from the last chapter. It finds the route with the fewest roads. From Home to Market that's the direct road: 1 road, 4 minutes. But Home to Bridge to Market is 2 roads and only 3 minutes. Breadth-first search treats a 1-minute road and an 8-minute road as the same one step, so it answers the wrong question: 4 minutes, where 3 is possible.

Always take the shortest road out of where you are. From Home, the shortest road is to Bridge (2). From Bridge, the shortest road to somewhere new is to Market (1). From Market, to School (5). From School, to Stadium (3). That reaches Stadium in 2 + 1 + 5 + 3 = 11 minutes. But Home to Bridge to Stadium is 2 + 8 = 10. Each step looked good on its own, and the whole drive still lost a minute: a short road now can lead the long way round.

Try every route, and keep the fastest. It's always right. Here, there are only a few routes. But a small grid of streets, 10 intersections by 10, has 48,620 routes of the shortest length from one corner to the other, and a real city has hundreds of thousands of intersections. Like listing every route in the last chapter, it's exponential.

What we tried Its answer The fastest Where it breaks
Fewest roads (breadth-first search) Home to Market, 4 minutes 3 minutes roads of different lengths
The shortest next road, every time Home to Stadium, 11 minutes 10 minutes a short road can lead the long way round
Every route always right 48,620 routes on a 10 by 10 grid, and far more in a city

The questions that lead to it

Which place's time are we sure of right now? Home: 0 minutes.

Of the places one road from Home, which time is already sure? Bridge, 2 minutes. Every other way to Bridge starts with a road from Home that's already longer (Market, 4), and roads never take less than 0 minutes, so nothing can sneak in under 2. Market's 4, though, isn't sure yet: going through Bridge might beat it, and it does, with 3.

So what if we repeat that? Of all the places reached but not yet sure, the one with the smallest time is always sure. Make it sure, look along its roads, update any time that gets better, and pick the smallest again.

We keep asking for "the smallest waiting time". Which structure from Module 6 hands back the smallest first? The emergency room's waiting list: a heap, which your language calls a priority queue. It hands back the place with the fewest minutes in O(log n), without sorting everyone.

How it got its name

This method was so useful that it got a name, after the computer scientist who worked it out in 1956, Edsger Dijkstra (read "DIKE-struh"): Dijkstra's algorithm. A place whose time is sure is settled. The route with the smallest total weight is, in textbooks, the shortest path.

  1. Of all the places reached but not yet settled, take the one with the smallest time. Settle it: that time is now final.
  2. From it, look along each road. If going this way reaches a neighbor faster than its best-known time, write down the new, smaller time, and note where it came from.

Why can a settled time never get better? Every other route out there starts from a place that's already at least as far away, and roads never take less than zero minutes. That's also why the algorithm needs weights of zero or more.

Here it is from Home:

Settle Its time (final) What it finds along its roads
Home 0 Market 4, Bridge 2
Bridge 2 Market 2 + 1 = 3, better than 4: write 3. Stadium 2 + 8 = 10
Market 3 School 3 + 5 = 8
School 8 Stadium 8 + 3 = 11, not better than 10: keep 10
Stadium 10 nothing new

Five snapshots of the town map, one per step of Dijkstra's algorithm from Home: in each, the places settled so far are filled in with their final minutes, Home 0, then Bridge 2, then Market 3, then School 8, then Stadium 10, while places still waiting show their best time so far, and a sixth panel highlights the fastest route to School, Home to Bridge to Market to School

Look at the School row: the shortest-next-road walk took that road to Stadium, for 11. Dijkstra's algorithm saw 11, compared it with the 10 it already had, and kept 10.

Dijkstra's algorithm in code

The waiting list is a priority queue (Fair Ties, Ready-Made: Priority Queues in Your Language): like the emergency room in Who's Next in the Emergency Room? Heaps, it hands back the most urgent entry first, here the one with the fewest minutes. When a place gets a better time, the code adds a new entry and, later, skips the old one if the place is already settled.

(string, string, int)[] roads = { ("Home", "Market", 4), ("Home", "Bridge", 2), ("Bridge", "Market", 1), ("Market", "School", 5), ("Bridge", "Stadium", 8), ("School", "Stadium", 3) };
Dictionary<string, List<(string To, int Minutes)>> town = new Dictionary<string, List<(string To, int Minutes)>>();
foreach ((string a, string b, int minutes) in roads)
{
    if (!town.ContainsKey(a)) town[a] = new List<(string To, int Minutes)>();
    if (!town.ContainsKey(b)) town[b] = new List<(string To, int Minutes)>();
    town[a].Add((b, minutes));
    town[b].Add((a, minutes));
}

Dictionary<string, int> settled = new Dictionary<string, int>();
Dictionary<string, int> best = new Dictionary<string, int> { ["Home"] = 0 };
Dictionary<string, string> cameFrom = new Dictionary<string, string>();
PriorityQueue<(string Place, int Minutes), int> waiting = new PriorityQueue<(string Place, int Minutes), int>();
waiting.Enqueue(("Home", 0), 0);

while (waiting.Count > 0)
{
    (string place, int minutes) = waiting.Dequeue();
    if (settled.ContainsKey(place))
    {
        continue;
    }
    settled[place] = minutes;
    foreach ((string to, int road) in town[place])
    {
        int total = minutes + road;
        if (!best.ContainsKey(to) || total < best[to])
        {
            best[to] = total;
            cameFrom[to] = place;
            waiting.Enqueue((to, total), total);
        }
    }
}

foreach (KeyValuePair<string, int> entry in settled)
{
    Console.WriteLine(entry.Key + ": " + entry.Value + " minutes");
}
List<string> route = new List<string> { "School" };
while (route[0] != "Home")
{
    route.Insert(0, cameFrom[route[0]]);
}
Console.WriteLine("Fastest way to School: " + string.Join(", ", route));
Home: 0 minutes
Bridge: 2 minutes
Market: 3 minutes
School: 8 minutes
Stadium: 10 minutes
Fastest way to School: Home, Bridge, Market, School
record Road(String to, int minutes) {}
record Stop(String place, int minutes) {}

Map<String, List<Road>> town = new HashMap<>();

void addRoad(String a, String b, int minutes) {
    town.computeIfAbsent(a, key -> new ArrayList<>()).add(new Road(b, minutes));
    town.computeIfAbsent(b, key -> new ArrayList<>()).add(new Road(a, minutes));
}

void main() {
    addRoad("Home", "Market", 4);
    addRoad("Home", "Bridge", 2);
    addRoad("Bridge", "Market", 1);
    addRoad("Market", "School", 5);
    addRoad("Bridge", "Stadium", 8);
    addRoad("School", "Stadium", 3);

    Map<String, Integer> settled = new LinkedHashMap<>();
    Map<String, Integer> best = new HashMap<>(Map.of("Home", 0));
    Map<String, String> cameFrom = new HashMap<>();
    PriorityQueue<Stop> waiting = new PriorityQueue<>(Comparator.comparingInt(Stop::minutes));
    waiting.add(new Stop("Home", 0));

    while (!waiting.isEmpty()) {
        Stop stop = waiting.remove();
        if (settled.containsKey(stop.place())) {
            continue;
        }
        settled.put(stop.place(), stop.minutes());
        for (Road road : town.get(stop.place())) {
            int total = stop.minutes() + road.minutes();
            if (!best.containsKey(road.to()) || total < best.get(road.to())) {
                best.put(road.to(), total);
                cameFrom.put(road.to(), stop.place());
                waiting.add(new Stop(road.to(), total));
            }
        }
    }

    for (Map.Entry<String, Integer> entry : settled.entrySet()) {
        IO.println(entry.getKey() + ": " + entry.getValue() + " minutes");
    }
    List<String> route = new ArrayList<>(List.of("School"));
    while (!route.get(0).equals("Home")) {
        route.add(0, cameFrom.get(route.get(0)));
    }
    IO.println("Fastest way to School: " + String.join(", ", route));
}
Home: 0 minutes
Bridge: 2 minutes
Market: 3 minutes
School: 8 minutes
Stadium: 10 minutes
Fastest way to School: Home, Bridge, Market, School
import heapq

roads = [("Home", "Market", 4), ("Home", "Bridge", 2), ("Bridge", "Market", 1), ("Market", "School", 5), ("Bridge", "Stadium", 8), ("School", "Stadium", 3)]
town = {}
for a, b, minutes in roads:
    town.setdefault(a, []).append((b, minutes))
    town.setdefault(b, []).append((a, minutes))

settled = {}
best = {"Home": 0}
came_from = {}
waiting = [(0, "Home")]

while waiting:
    minutes, place = heapq.heappop(waiting)
    if place in settled:
        continue
    settled[place] = minutes
    for to, road in town[place]:
        total = minutes + road
        if to not in best or total < best[to]:
            best[to] = total
            came_from[to] = place
            heapq.heappush(waiting, (total, to))

for place, minutes in settled.items():
    print(f"{place}: {minutes} minutes")
route = ["School"]
while route[0] != "Home":
    route.insert(0, came_from[route[0]])
print("Fastest way to School: " + ", ".join(route))
Home: 0 minutes
Bridge: 2 minutes
Market: 3 minutes
School: 8 minutes
Stadium: 10 minutes
Fastest way to School: Home, Bridge, Market, School
const roads = [["Home", "Market", 4], ["Home", "Bridge", 2], ["Bridge", "Market", 1], ["Market", "School", 5], ["Bridge", "Stadium", 8], ["School", "Stadium", 3]];
const town = new Map();
for (const [a, b, minutes] of roads) {
  town.set(a, [...(town.get(a) ?? []), [b, minutes]]);
  town.set(b, [...(town.get(b) ?? []), [a, minutes]]);
}

// No built-in priority queue: find the entry with the fewest minutes by scanning.
function takeSmallest(waiting) {
  let smallest = 0;
  for (let i = 1; i < waiting.length; i++) {
    if (waiting[i][1] < waiting[smallest][1]) {
      smallest = i;
    }
  }
  return waiting.splice(smallest, 1)[0];
}

const settled = new Map();
const best = new Map([["Home", 0]]);
const cameFrom = new Map();
const waiting = [["Home", 0]];

while (waiting.length > 0) {
  const [place, minutes] = takeSmallest(waiting);
  if (settled.has(place)) {
    continue;
  }
  settled.set(place, minutes);
  for (const [to, road] of town.get(place)) {
    const total = minutes + road;
    if (!best.has(to) || total < best.get(to)) {
      best.set(to, total);
      cameFrom.set(to, place);
      waiting.push([to, total]);
    }
  }
}

for (const [place, minutes] of settled) {
  console.log(`${place}: ${minutes} minutes`);
}
const route = ["School"];
while (route[0] !== "Home") {
  route.unshift(cameFrom.get(route[0]));
}
console.log(`Fastest way to School: ${route.join(", ")}`);
Home: 0 minutes
Bridge: 2 minutes
Market: 3 minutes
School: 8 minutes
Stadium: 10 minutes
Fastest way to School: Home, Bridge, Market, School
const roads: [string, string, number][] = [["Home", "Market", 4], ["Home", "Bridge", 2], ["Bridge", "Market", 1], ["Market", "School", 5], ["Bridge", "Stadium", 8], ["School", "Stadium", 3]];
const town = new Map<string, [string, number][]>();
for (const [a, b, minutes] of roads) {
  town.set(a, [...(town.get(a) ?? []), [b, minutes]]);
  town.set(b, [...(town.get(b) ?? []), [a, minutes]]);
}

// No built-in priority queue: find the entry with the fewest minutes by scanning.
function takeSmallest(waiting: [string, number][]): [string, number] {
  let smallest = 0;
  for (let i = 1; i < waiting.length; i++) {
    if (waiting[i][1] < waiting[smallest][1]) {
      smallest = i;
    }
  }
  return waiting.splice(smallest, 1)[0];
}

const settled = new Map<string, number>();
const best = new Map<string, number>([["Home", 0]]);
const cameFrom = new Map<string, string>();
const waiting: [string, number][] = [["Home", 0]];

while (waiting.length > 0) {
  const [place, minutes] = takeSmallest(waiting);
  if (settled.has(place)) {
    continue;
  }
  settled.set(place, minutes);
  for (const [to, road] of town.get(place) ?? []) {
    const total = minutes + road;
    if (!best.has(to) || total < best.get(to)!) {
      best.set(to, total);
      cameFrom.set(to, place);
      waiting.push([to, total]);
    }
  }
}

for (const [place, minutes] of settled) {
  console.log(`${place}: ${minutes} minutes`);
}
const route: string[] = ["School"];
while (route[0] !== "Home") {
  route.unshift(cameFrom.get(route[0])!);
}
console.log(`Fastest way to School: ${route.join(", ")}`);
Home: 0 minutes
Bridge: 2 minutes
Market: 3 minutes
School: 8 minutes
Stadium: 10 minutes
Fastest way to School: Home, Bridge, Market, School

C# has PriorityQueue<TElement, TPriority>, Java PriorityQueue and Python the heapq functions. JavaScript has no built-in priority queue, so the JavaScript and TypeScript tabs find the smallest entry by scanning the waiting list: fine for a town, slow for a country. A heap you write yourself, as in Who's Next in the Emergency Room? Heaps, makes each pick O(log n) there too.

The places print in the order they're settled, which is also the order of their times. The route comes from cameFrom: School came from Market, Market from Bridge, Bridge from Home. Following those notes backward and turning the list around gives the route.

Try it. Change the Bridge-to-Market road from 1 minute to 5 and run it again. Market's time becomes 4, by the direct road, and School's becomes 9.

Fewest steps or least time?

Breadth-first search isn't wrong; it answers a different question. When every edge counts the same, it's simpler and faster, and it's the right tool.

The question Use Why
The fewest stops, hops or transfers Breadth-first search Every edge counts as one step, and BFS is simpler and faster
The least total time, distance or cost, when edges differ Dijkstra's algorithm It adds up the weights and always settles the closest place first
Some edges have negative weights Neither A negative edge can make a settled time wrong; textbooks use the Bellman-Ford algorithm for this

Cost card

The heap is what makes it fast: without it, finding the closest waiting place means reading the whole waiting list every time.

What it does Big-O The everyday reason
Fastest times to every place, with a priority queue O((V + E) log V) time Every road can add an entry to the waiting list, and each entry costs about log V to put in or take out
The same, finding the smallest by scanning O(V²) time Each of the V places scans the whole waiting list
Remember times, routes and the waiting list O(V + E) memory A time and a "came from" note per place, and at most one waiting entry per road

Check yourself

2 questions to try on the lesson page.

So what

You now know what a GPS does when it "calculates a route": it settles the nearest place, again and again, until it reaches you, with a heap handing it the nearest place each time. Whenever edges have costs and you want the cheapest total, Dijkstra's algorithm is where to start.

Key terms

Cheat sheets

Related