---
title: "How Do Maps Find the Fastest Route? Dijkstra's Algorithm"
description: "Dijkstra's algorithm step by step on a small town map, why greedy shortcuts fail, and how A* checks far fewer places, all run in Python."
slug: dijkstras-algorithm-fastest-route
canonical: https://learn.modernagecoders.com/blog/dijkstras-algorithm-fastest-route/
date: 2026-09-28
dateModified: 2026-09-28
category: "Programming"
tags: ["Algorithms", "Graphs", "Python", "Computer Science"]
keywords: ["dijkstra's algorithm", "shortest path algorithm", "how does google maps find the fastest route", "dijkstra algorithm python", "a star algorithm", "graph algorithms for beginners", "how do map apps work"]
readTime: "7 min read"
author: "Modern Age Coders Team"
---
# How Do Maps Find the Fastest Route? Dijkstra's Algorithm

> Dijkstra's algorithm step by step on a small town, two shortcuts that give the wrong answer, and A*, the variant that aims at the goal, all run and measured in Python.

![How maps find the fastest route: a dotted route line from a start point to a map pin](/images/blog/dijkstras-algorithm-fastest-route/00-hero.png)

*By Modern Age Coders Team · 2026-09-28 · 7 min read*

**Quick answer:** Map apps model roads as a weighted graph and find the fastest route with shortest-path algorithms based on Dijkstra's algorithm, devised in 1956. It repeatedly settles the closest unsettled place, whose time can then never improve, and updates its neighbours. On our town map it found a 7-minute route, while always taking the quickest next road gave 11 minutes and the fewest-roads route 16. A* adds an estimate of the distance to go: on a 10,000-place grid it checked 467 places instead of 6,420 for the same answer.

Ask a map app for directions and it picks the fastest route from millions of possible roads in a moment. The classic method behind route finding is Dijkstra's algorithm, and it is simple enough to follow by hand on a small map, and to write in about twenty lines of Python.

This guide runs Dijkstra's algorithm on a small town, step by step, then compares it with two tempting shortcuts that give the wrong answer. It ends with A*, the faster variant used in games and navigation, measured on a 10,000-place grid. Every result below comes from running the code.

## The problem: a map is a graph

To a computer, a road map is a **graph**: places are *nodes*, roads are *edges*, and each edge has a *weight*, here the travel time in minutes. Finding the fastest route means finding the path between two nodes with the smallest total weight. Here is our town:

**town.py**

```python
# A small town: travel times in minutes along each road (roads go both ways)
roads = [
    ("Home", "Shop", 2), ("Home", "Park", 4), ("Home", "Library", 13),
    ("Shop", "Park", 1), ("Shop", "Market", 3), ("Park", "Library", 5),
    ("Library", "Market", 4), ("Library", "School", 3), ("Market", "School", 2),
]
graph = {}
for a, b, minutes in roads:
    graph.setdefault(a, {})[b] = minutes
    graph.setdefault(b, {})[a] = minutes
```

![A small town with six places and nine roads labelled with travel times; the fastest route from Home to School is Home -> Shop -> Market -> School, 7 minutes, highlighted](/images/blog/dijkstras-algorithm-fastest-route/01-town.png)

*Six places, nine roads, and one fastest route.*

## Dijkstra's algorithm, step by step

In 1956, the Dutch computer scientist Edsger Dijkstra wanted a problem that non-programmers could understand, to show off a new computer in Amsterdam. He later said he designed the shortest-path algorithm "in about twenty minutes", sitting on a café terrace, and it was published in 1959. The idea:

1. Give the start a time of 0 and every other place a time of infinity (not yet reached).
2. Pick the unsettled place with the smallest time and **settle** it: its time is now final.
3. For each road out of it, see if going that way reaches a neighbour faster than its current best time. If so, update it.
4. Repeat until the destination is settled.

The key insight is step 2. Because all travel times are positive, once a place is the closest unsettled one, no other route can ever reach it more quickly, so its time is final. In code, a *priority queue* (Python's `heapq`) hands back the closest place each time:

**dijkstra.py**

```python
import heapq
from town import graph

def dijkstra(graph, start, goal):
    best = {start: 0}               # fastest known time to each place
    came_from = {}
    queue = [(0, start)]
    settled = []
    while queue:
        time, place = heapq.heappop(queue)     # always expand the closest unsettled place
        if place in settled:
            continue
        settled.append(place)
        if place == goal:
            break
        for nxt, minutes in graph[place].items():
            new_time = time + minutes
            if new_time < best.get(nxt, float("inf")):
                best[nxt] = new_time
                came_from[nxt] = place
                heapq.heappush(queue, (new_time, nxt))
    route = [goal]
    while route[-1] != start:
        route.append(came_from[route[-1]])
    return best[goal], route[::-1], settled

if __name__ == "__main__":
    minutes, route, settled = dijkstra(graph, "Home", "School")
    print("settled in this order:", " -> ".join(settled))
    print(f"fastest route: {' -> '.join(route)} ({minutes} minutes)")
```

**Output**

```text
settled in this order: Home -> Shop -> Park -> Market -> School
fastest route: Home -> Shop -> Market -> School (7 minutes)
```

![Table of Dijkstra's algorithm on the town: it settles Home at 0, Shop at 2, Park at 3, Market at 5 and School at 7, updating the best known times after each step](/images/blog/dijkstras-algorithm-fastest-route/02-steps.png)

*Each row is one settle. Times only ever go down until they are final.*

Dijkstra settled Home, Shop, Park, Market and then School, in order of distance from Home, and found Home -> Shop -> Market -> School in 7 minutes. Notice that it never settled the Library: by the time School was reached, the Library was known to be further away, so it was not needed.

## Two tempting shortcuts, and why they fail

It is worth seeing why a smarter method is needed. The first shortcut: from wherever you are, take the quickest road you have not used yet. This is a **greedy** strategy:

**greedy.py**

```python
from town import graph

# A tempting shortcut: always take the quickest road from where you are now
place, route, total = "Home", ["Home"], 0
while place != "School":
    options = {p: m for p, m in graph[place].items() if p not in route}
    place = min(options, key=options.get)
    total += options[place]
    route.append(place)
print(f"greedy route: {' -> '.join(route)} ({total} minutes)")
```

**Output**

```text
greedy route: Home -> Shop -> Park -> Library -> School (11 minutes)
```

The second: take the route with the fewest roads, which is what a **breadth-first search** finds when it ignores travel times:

**fewest.py**

```python
from collections import deque
from town import graph

# Fewest roads (ignoring how long each one takes): breadth-first search
queue, seen = deque([["Home"]]), {"Home"}
while queue:
    path = queue.popleft()
    if path[-1] == "School":
        break
    for nxt in graph[path[-1]]:
        if nxt not in seen:
            seen.add(nxt)
            queue.append(path + [nxt])
minutes = sum(graph[a][b] for a, b in zip(path, path[1:]))
print(f"fewest roads: {' -> '.join(path)} ({len(path) - 1} roads, {minutes} minutes)")
```

**Output**

```text
fewest roads: Home -> Library -> School (2 roads, 16 minutes)
```

![Three strategies on the same town: Dijkstra's fastest route takes 7 minutes, always taking the quickest next road takes 11 minutes, and the route with fewest roads takes 16 minutes](/images/blog/dijkstras-algorithm-fastest-route/03-three.png)

*Only Dijkstra looks at the whole picture.*

The greedy route took 11 minutes: the 1-minute road from the Shop to the Park looked attractive, but it led the wrong way. The fewest-roads route used only 2 roads but took 16 minutes, because one of them is a long 13-minute road. Dijkstra's 7 minutes beats both, because it compares every possibility in order of total time rather than trusting one step at a time.

> **The limits of Dijkstra**

> Dijkstra's algorithm needs every weight to be zero or positive, which is true for travel times. If some edges could have negative weights, a different method such as Bellman-Ford is needed. Our guide to [learning data structures and algorithms](/blog/how-to-start-learning-data-structures-and-algorithms) covers where graph algorithms fit in.

## A*: aiming at the goal

Dijkstra explores outwards evenly in every direction, like ripples in a pond, even away from where you are going. **A*** (pronounced A-star) adds an estimate of the time still to go, such as the straight-line or grid distance to the goal, and explores the places that look most promising first. As long as the estimate never overestimates, A* still finds the fastest route. We compared them on a 100 × 100 grid town:

**astar.py**

```python
import heapq, random

# A 100 x 100 grid of streets: most blocks take 1 minute, some busy ones take 4
N = 100
rng = random.Random(3)
cost = [[1 if rng.random() < 0.8 else 4 for _ in range(N)] for _ in range(N)]
start, goal = (50, 20), (50, 80)                # across the middle of town

def search(use_estimate):
    best, queue, settled = {start: 0}, [(0, 0, start)], set()
    while queue:
        _, time, (r, c) = heapq.heappop(queue)
        if (r, c) in settled:
            continue
        settled.add((r, c))
        if (r, c) == goal:
            return time, len(settled)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N:
                t = time + cost[nr][nc]
                if t < best.get((nr, nc), float("inf")):
                    best[(nr, nc)] = t
                    # A*: add a lower bound on the time still to go (every step costs at least 1)
                    guess = (abs(goal[0] - nr) + abs(goal[1] - nc)) if use_estimate else 0
                    heapq.heappush(queue, (t + guess, t, (nr, nc)))

for name, flag in [("Dijkstra", False), ("A*", True)]:
    time, visited = search(flag)
    print(f"{name:<9} fastest time {time} minutes, places settled {visited:,} of {N * N:,}")
```

**Output**

```text
Dijkstra  fastest time 72 minutes, places settled 6,420 of 10,000
A*        fastest time 72 minutes, places settled 467 of 10,000
```

![On a 100 by 100 grid, Dijkstra settled 6,420 places and A* settled 467 places, and both found the same 72-minute route](/images/blog/dijkstras-algorithm-fastest-route/04-astar.png)

*Same answer, a fraction of the work.*

Both found the same 72-minute route, but A* settled 467 places while Dijkstra settled 6,420, about 14 times fewer. How much A* helps depends on how good the estimate is. When we first tried a grid where every street took 1 to 5 minutes at random, corner to corner, the estimate was weak and A* settled 9,994 places against Dijkstra's 10,000. Real navigation apps go further still, using live traffic data and precomputed shortcuts across the road network, but Dijkstra's idea is at the heart of it.

## Where shortest paths are used

- **Navigation apps** for driving, walking and public transport.
- **Games:** characters finding their way round obstacles, usually with A*.
- **The internet:** routers choosing paths for data. A widely used routing protocol, OSPF, uses Dijkstra's algorithm.
- **Deliveries and logistics:** planning routes for vans and couriers.

> Settle the closest place first, and never look back. That one rule finds the fastest route.

## How we teach it

Dijkstra's algorithm suits a principle on our [how we teach](/how-we-teach) page: trace line by line until the student can predict every step. Filling in the settle table by hand on a small map, then checking it against the code, is exactly that. Seeing the same problem solved three ways, greedy, fewest roads and Dijkstra, makes clear why the algorithm works. Our [data structures and algorithms course](/data-structures-and-algorithms-course) runs one to one or in small groups of 5 to 10.

[Book a free class](/book-demo) [Book a priority demo](/book-demo)

## Frequently asked questions

**How do map apps find the fastest route?**

They treat the road network as a graph of places and roads weighted by travel time, and use shortest-path algorithms built on Dijkstra's algorithm or A*, combined with live traffic data and precomputed shortcuts to make it fast on huge maps.

**What is Dijkstra's algorithm?**

An algorithm for finding the shortest or fastest path in a graph with non-negative weights. It repeatedly settles the closest unsettled node and updates its neighbours, until the destination is settled. It was devised by Edsger Dijkstra in 1956.

**Why doesn't always taking the shortest next road work?**

Because a quick road can lead in the wrong direction. In our example, always taking the quickest next road gave an 11-minute route, while Dijkstra found a 7-minute one.

**What is the difference between Dijkstra and A*?**

A* adds an estimate of the remaining distance to the goal, so it explores promising directions first. With a good estimate it checks far fewer places: in our grid test, 467 instead of 6,420, for the same answer.

**Does Dijkstra's algorithm work with negative weights?**

No. It relies on every weight being zero or positive. Graphs with negative weights need other algorithms, such as Bellman-Ford.

**What is a graph in computer science?**

A set of nodes connected by edges. Maps, social networks, the internet and many other things can be modelled as graphs, which is why graph algorithms are so widely used.

**Is Dijkstra's algorithm hard to learn?**

The idea is simple enough to follow by hand on a small map. Coding it needs loops, dictionaries and a priority queue, which makes it a good intermediate project and a common topic in olympiads and interviews.

---

*Source: https://learn.modernagecoders.com/blog/dijkstras-algorithm-fastest-route/*