How Google Maps Finds the Fastest Route

You open Google Maps. You type “Bangalore to Mysore.” In under a second, it shows you the fastest route — not the shortest road, but the one that accounts for traffic, tolls, highway speeds, and that weird bottleneck near Ramanagara. You’ve used this a thousand times without thinking about it.

Behind that blue line is an algorithm invented in 1956 by a Dutch computer scientist named Edsger Dijkstra. He reportedly designed it in 20 minutes while sitting at a café, without a computer. It’s called Dijkstra’s Algorithm, and it’s one of the most important algorithms ever created.

The Real-World Problem

Why “shortest distance” isn’t the same as “fastest route”

If you draw a straight line from Bangalore to Mysore, it’s about 140 km. But Google Maps doesn’t draw straight lines. It considers roads — and not all roads are equal. A 10 km stretch on NH-275 at 100 km/h takes 6 minutes. A 10 km stretch through a town at 20 km/h takes 30 minutes. Same distance, wildly different travel times.

This is why the algorithm needs weighted edges. Every road segment has a “cost” — not just its length, but how long it takes to travel. Heavy traffic? Higher cost. Highway with no signals? Lower cost. Under construction? Much higher cost.

The Core Idea

Think of it like spreading water

Imagine you pour water at your starting city. The water flows along all roads simultaneously, but it flows slower on heavier roads (high-cost edges) and faster on lighter roads (low-cost edges). The first drop of water to reach the destination — that’s your shortest path. It found the route with the least total resistance.

Dijkstra’s algorithm does exactly this, but methodically. It keeps a list of “tentative distances” — the cheapest known cost to reach each city — and updates them as it explores. It always picks the unvisited city with the lowest tentative distance next. This greedy choice is what makes it correct — it guarantees that once a city is “visited,” its shortest distance is final.

See It In Action

Interactive Demo: Find the shortest path

Below is a randomly generated map of cities with weighted roads. Click any city to set your start, then click another for the destination. Watch Dijkstra explore — yellow means “considering,” green means “finalized.” The numbers inside each circle show the shortest known distance from the start.

Things to notice: the algorithm doesn’t go straight for the destination. It expands outward from the start, visiting nearby cheap cities first. It might explore in the “wrong” direction before finding the optimal path — that’s normal. It’s being thorough, not wasteful.

The Algorithm Step by Step

Here’s what Dijkstra’s algorithm does, in plain language:

1. Setup. Assign every city a tentative distance of ∞ (infinity), except the start which gets 0. Put all cities in an “unvisited” set.

2. Pick the cheapest. From all unvisited cities, pick the one with the smallest tentative distance. Call it “current.”

3. Check its neighbours. For each road from “current” to a neighbour, calculate: current’s distance + road weight. If this is cheaper than the neighbour’s existing tentative distance, update it. This is called relaxation — you’ve found a cheaper route to that neighbour.

4. Mark as visited. Move “current” to the visited set. Its distance is now final — guaranteed to be the shortest.

5. Repeat. Go back to step 2. Stop when you’ve visited the destination (or all reachable cities).

The Code

function dijkstra(graph, start, end) {
  const dist = {};    // shortest known distance to each node
  const prev = {};    // previous node on the best path
  const visited = new Set();

  // Step 1: Everything starts at infinity, except the start
  for (const node of graph.nodes) {
    dist[node] = Infinity;
    prev[node] = null;
  }
  dist[start] = 0;

  while (true) {
    // Step 2: Pick the unvisited node with smallest distance
    let current = null, minDist = Infinity;
    for (const node of graph.nodes) {
      if (!visited.has(node) && dist[node] < minDist) {
        current = node;
        minDist = dist[node];
      }
    }

    if (current === null || current === end) break;

    // Step 4: Mark as visited
    visited.add(current);

    // Step 3: Check all neighbours (relaxation)
    for (const { neighbour, weight } of graph.edges[current]) {
      const newDist = dist[current] + weight;
      if (newDist < dist[neighbour]) {
        dist[neighbour] = newDist;    // found a cheaper route!
        prev[neighbour] = current;    // remember how we got here
      }
    }
  }

  // Reconstruct the path by walking backwards from end
  const path = [];
  let node = end;
  while (node !== null) {
    path.unshift(node);
    node = prev[node];
  }

  return { distance: dist[end], path };
}

The most important line is the relaxation: if (newDist < dist[neighbour]). This is where the algorithm discovers a better route — “I can reach you cheaper through this road than any road I’ve tried before.”

Add Traffic, Watch It Reroute

Interactive Demo: Traffic simulation

This is a grid of city intersections with a route from 🏠 (top-left) to 🏢 (bottom-right). Click on any road to add traffic — increasing its weight. Watch how the blue shortest path changes instantly. This is exactly what Google Maps does when it detects congestion — it re-runs the algorithm with updated weights.

Try this experiment: add heavy traffic to every road on the direct path. Watch how the algorithm finds a longer but faster detour — sometimes going sideways or even upward before heading down. This is why Google Maps sometimes suggests a route that “looks” longer on the map but actually saves time.

Why Not Just Try Every Route?

For a map with n cities, the number of possible routes grows exponentially. With just 20 cities, there are trillions of possible paths. Checking every one would take longer than the actual drive.

Dijkstra’s algorithm is smart because it never re-processes a city. Once a city is marked “visited,” its shortest distance is guaranteed correct. This makes it O(V²) in the simple version — for a map with 1,000 intersections, that’s about 1 million operations. A computer does that in milliseconds.

Google Maps actually uses an even faster variant called A* (A-star), which adds a clever trick: it uses the straight-line distance to the destination as a “hint” to guide the search toward the goal, rather than exploring equally in all directions. But the foundation is still Dijkstra.

Where Else Is This Used?

Network routing. When you load this webpage, your data packets traveled through dozens of routers. Each router uses a variant of Dijkstra (called OSPF — Open Shortest Path First) to find the fastest path through the internet.

Video games. When an enemy character walks toward you in a game, it’s running a pathfinding algorithm — usually A*, Dijkstra’s faster cousin — to navigate around obstacles.

Social networks. “Degrees of separation” — finding the shortest connection between two people — is a graph traversal problem. LinkedIn’s “how you’re connected” feature is this idea in action.

Airline booking. When Skyscanner finds “cheapest flights with 1 stop,” it’s solving a shortest-path problem where cities are airports and weights are ticket prices.

The Limitation

What Dijkstra can’t handle

Dijkstra’s algorithm has one strict requirement: all weights must be non-negative. It assumes that adding a road to your path can never make it cheaper (you can’t have a road that subtracts from your travel time). This is a reasonable assumption for physical roads, but not for all problems.

In finance, for example, currency exchange graphs can have “negative cycles” — a series of trades that generates free profit. Dijkstra fails here. You’d need Bellman-Ford or Floyd-Warshall instead. But for routing — the problem it was designed for — it’s perfect.