How Does GPS Find the Shortest Route?

I wrote this while studying CS50 and learning algorithms in C. I came across Dijkstra's algorithm and wanted to understand it better, so I decided to try writing it myself.

When I use Google Maps, I just enter where I want to go and follow the route. I never really thought about how it chooses the route. But for a computer, finding a route is actually a problem.

Turning a map into a graph

We can represent a map as a graph. Places can be nodes, roads can be edges, and each road can have a weight. The weight can be the distance between two places.

For example:

A --4-- B
|       |
2       5
|       |
C --1-- D

If we want to go from A to D, we have two routes:

A → B → D = 9
A → C → D = 3

So the shorter route is A → C → D.

This is easy with four places. But a real map has a lot more roads. We can't just check every possible route.

This is where Dijkstra's algorithm is useful.

How does Dijkstra work?

We start from the place we are at.

Its distance is 0. We don't know the distances to the other places yet, so we use infinity.

A = 0
B = ∞
C = ∞
D = ∞

From A, we can go to B with a cost of 4 and C with a cost of 2.

C is closer, so we check C.

From C to D costs 1:

2 + 1 = 3

Now we know that D can be reached with a cost of 3.

The main idea is simple: we check the closest place and see if we can find a shorter route to its neighbors.

In C, this part looks like:

int new_distance = current_distance + weight;

if (new_distance < distances[neighbor])
{
    distances[neighbor] = new_distance;
}

If the new route is shorter, we update the distance.

My C implementation

Since I'm learning C in CS50, I wanted to implement Dijkstra in C instead of only reading about it.

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

#define N 4

int find_min(int distances[], bool visited[])
{
    int min = INT_MAX;
    int min_index = -1;

    for (int i = 0; i < N; i++)
    {
        if (!visited[i] && distances[i] < min)
        {
            min = distances[i];
            min_index = i;
        }
    }

    return min_index;
}

void dijkstra(int graph[N][N], int start)
{
    int distances[N];
    bool visited[N];

    for (int i = 0; i < N; i++)
    {
        distances[i] = INT_MAX;
        visited[i] = false;
    }

    distances[start] = 0;

    for (int i = 0; i < N - 1; i++)
    {
        int current = find_min(distances, visited);

        visited[current] = true;

        for (int neighbor = 0; neighbor < N; neighbor++)
        {
            if (graph[current][neighbor] != 0 &&
                !visited[neighbor] &&
                distances[current] != INT_MAX &&
                distances[current] + graph[current][neighbor]
                    < distances[neighbor])
            {
                distances[neighbor] =
                    distances[current] + graph[current][neighbor];
            }
        }
    }

    for (int i = 0; i < N; i++)
    {
        printf("%d -> %d = %d\n", start, i, distances[i]);
    }
}

int main(void)
{
    int graph[N][N] =
    {
        {0, 4, 2, 0},
        {4, 0, 0, 5},
        {2, 0, 0, 1},
        {0, 5, 1, 0}
    };

    dijkstra(graph, 0);
}

The code keeps the distances we know and updates them when it finds a shorter route.

So, does GPS use Dijkstra?

Not exactly.

Real maps are much more complicated. There can be traffic, closed roads, one-way streets and speed limits. Because of this, real navigation systems can use other algorithms too. One example is A*. It is similar to Dijkstra, but it also looks at where the destination is and can focus the search in that direction.