# How do map providers like Google calculate the distance between two coordinates and find turn by turn directions?

I have searched on how Google or any map provider calculates distance between two coordinates. The closest I could find is Haversine formula.

If I draw a straight line between two points, then Haversine formula can be helpful. But since no one will travel straight and typically move through the streets, I want to know if there are any methods to calculate turn by turn points and see how to find multiple ways to travel to the destination from the source.

Right now my idea is

1. Have the two coordinates within a map window.
2. Make an algorithm detect the white lines (path) in the window.
3. Make it understand how they are connected.
4. Feed it to an algorithm to solve the Travelling Salesman Problem to find the best path between them.

But these things see very memory and process intensive. Even with the knowledge that Google has the powerhouse to process, to serve so many directions and distance matrix in fractions of seconds in amazing. I want to know if there are different approaches to this?

Roads maps are well defined and you can access them online. For example you can visit OpenStreetMap to download road network of a given region.

Such a road network definition contains nodes (junctions) with lat/lon coordinates and edges between nodes (roads). An edge is defined by a connection of two nodes. Edges can represent one-way roads: you need to define double ways as two edges going in both ways. Haversine formula gives you the straight distance between two nodes: the length of the edge.

This definition of a road network gives you a graph (in the mathematical point of view) and is largely covered by the literature. You can search the graph and compute many of its parameters.

From a road network definition you can run shortest path algorithm to find the closest way between two nodes. From a given coordinate you can either pick the closest node or get the closest edge (and compute distance to the edge and the coordinates of the perpendicular projection point).

Algorithms like A* and Dijkstra are not so time consuming and you can find shortest path efficiently.

Obviously the way Google store their information is not published, but from the Directions API I would make the following educated guesses:

1. The roads/paths are stored as a graph database