First, the road network must be modeled as a graph G—that is, a collection of vertices and edges. Each intersection of two roads is a vertex of G, and each stretch of road between two intersections is an edge. A value (for example, a distance measured in kilometers or a travel time measured in hours) can be assigned to each edge, giving a weighted graph. Finding the shortest path between two vertices—an origin O and a destination Dest—then means finding the sequence of edges connecting O to Dest with the smallest total weight.
In 1959, Dutch computer scientist Edsger Dijkstra proposed a highly efficient algorithm for doing so. It uses the principle formulated by mathematician Richard Bellman: every subpath of an optimal path is itself optimal.
In other words, if the shortest path from O to Dest is O-A-D-E-Dest, then the shortest path from A to E is A-D-E… and conversely. The shortest path between the origin and the destination can therefore be found by moving through the graph one vertex at a time and, at each iteration, keeping track of the shortest path from the origin to every vertex in the graph.
