Find the shortest path: Algorithm behind GPS

Dijkstra’s Algorithm

Photo by henry perks on Unsplash

Today, we will introduce the basic algorithm widely implemented in GPS and map, Dijkstra’s algorithm.

Before we jump into it, let’s see what the weighted-edge graph is.

Weighted-edge graph

In reality, when we move from point to point, the length of the path is always one factor. Unlike the edge graph, the weighted-edge graph considers not just length but more similar to the “difficulty” of moving between points.

Take the above picture as an example. The edge from 0 to 1 is 5, from 0 to 3 is 6. When we want to find the shortest path from 0 to 3, we will choose 0 to 3 instead of 0 to 1 to 3 because the total weight for the path of 0 to 3 is only 6. If you move from 0 to 1 to 3, the total weight is 8.

0 to 3 is the shortest path

Let’s implement these properties into Python.

First, the directed-edge