Which algorithm does Google maps use to compute the direction between 2 points?

Question

I wonder which algorithm Google maps use to compute the direction between 2 points ? Has Google ever mentioned about it ?

p/s : I am asking the algorithm which google use to find the shortest route between 2 points.

Answer 1

To the best of my knowledge Google has never publicly stated which algorithm it uses of P2P queries. Although the current state of the art from the literature in terms of query times is the Hub labelling algorithm proposed by Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . A through and excellently written survey of the field was recently published as a Microsoft technical report http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .

The short version is...

The Hub labelling algorithm provides the fastest queries for static road networks but requires a large amount of ram to run (18 GiB).

Transit node routing is slightly slower, although, it only requires around 2 GiB of memory and has a quicker preprocessing time.

Contraction Hierarchies provide a nice trade off between quick preprocessing times, low space requirements (0.4 GiB) and fast query times.

No one algorithm is completely dominate...

This Google tech talk by Peter Sanders may be of interest

https://www.youtube.com/watch?v=-0ErpE8tQbw

Also this talk by Andrew Goldberg

https://www.youtube.com/watch?v=WPrkc78XLhw

An open source implementation of contraction hierarchies is available from Peter Sanders research group website at KIT. http://algo2.iti.kit.edu/english/routeplanning.php

Answer 2

If you mean google maps direction api and the shortest route between 2 points then it's a graph-theory problem that can be solved using the dijktstra algorithm. It' a DFS with a backtracking.

Answer 3

Google maps is using Dijkstra's Shortest Path Algorithm. It calculates the connections between pairs of elements or so called nodes. The connection between nodes are called edges. Each edge has a weight. The weight of an edge can represent distance, time, or anything that models the "connection" between the pair of nodes it connects. These weights are essential for Dijkstra's Algorithm. In that way you can find the shortest path between nodes. Particularly, you can find the shortest path from a node (called the "source node") to all other nodes, producing a shortest-path tree.

Answer 4

Google map is using some very sophisticated algorithm. It might be any heuristics such as A*; but, it is definitely not Dijkstra's algorithm. My finding;

1] Many times it shows path of less traffic, which changes with time but Dijkstra algorithm would give a single path in all situations.

2] Me, and my friends were visiting some place; we all have started google map at the same time. If google map was giving optimal shortest path then our maps must had provided us the same path; but it did not happen. It means they are not using any exact algorithm.

Udacity data structure and Algorithm nanodegree claims that Google is using an algorithm similar to A* algorithm; however, it requires citation. You may also visit quora discussion

Answer 5

Google Maps relies on various algorithms and technologies to provide accurate and efficient mapping, navigation, and location-based services. Google has not publicly disclosed the exact algorithms and techniques used in Google Maps.

• For routing algorithms, they might use Dijkstra's algorithm and the A (A-star) algorithm.
• Dijkstra’s Algorithm is commonly used in network routing protocols
  and is a foundational algorithm for finding the shortest path in a graph.
• Fall back of Dijkstra’s Algorithm: As the number of nodes are infinite or uncountable , it fails to increase the time and space
  complexity.
• A* Algorithm is an extension of Dijkstra’s algorithm that includes heuristics to improve performance, often used in pathfinding and graph traversal and it focuses only on the destination nodes.

Answer 6

You should always check on the android source code for doubts like this.

Based on http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf

 private static void computeDistanceAndBearing(double lat1, double lon1,
        double lat2, double lon2, float[] results) {


        int MAXITERS = 20;
        // Convert lat/long to radians
        lat1 *= Math.PI / 180.0;
        lat2 *= Math.PI / 180.0;
        lon1 *= Math.PI / 180.0;
        lon2 *= Math.PI / 180.0;

        double a = 6378137.0; // WGS84 major axis
        double b = 6356752.3142; // WGS84 semi-major axis
        double f = (a - b) / a;
        double aSqMinusBSqOverBSq = (a * a - b * b) / (b * b);

        double L = lon2 - lon1;
        double A = 0.0;
        double U1 = Math.atan((1.0 - f) * Math.tan(lat1));
        double U2 = Math.atan((1.0 - f) * Math.tan(lat2));

        double cosU1 = Math.cos(U1);
        double cosU2 = Math.cos(U2);
        double sinU1 = Math.sin(U1);
        double sinU2 = Math.sin(U2);
        double cosU1cosU2 = cosU1 * cosU2;
        double sinU1sinU2 = sinU1 * sinU2;

        double sigma = 0.0;
        double deltaSigma = 0.0;
        double cosSqAlpha = 0.0;
        double cos2SM = 0.0;
        double cosSigma = 0.0;
        double sinSigma = 0.0;
        double cosLambda = 0.0;
        double sinLambda = 0.0;

        double lambda = L; // initial guess
        for (int iter = 0; iter < MAXITERS; iter++) {
            double lambdaOrig = lambda;
            cosLambda = Math.cos(lambda);
            sinLambda = Math.sin(lambda);
            double t1 = cosU2 * sinLambda;
            double t2 = cosU1 * sinU2 - sinU1 * cosU2 * cosLambda;
            double sinSqSigma = t1 * t1 + t2 * t2; // (14)
            sinSigma = Math.sqrt(sinSqSigma);
            cosSigma = sinU1sinU2 + cosU1cosU2 * cosLambda; // (15)
            sigma = Math.atan2(sinSigma, cosSigma); // (16)
            double sinAlpha = (sinSigma == 0) ? 0.0 :
                cosU1cosU2 * sinLambda / sinSigma; // (17)
            cosSqAlpha = 1.0 - sinAlpha * sinAlpha;
            cos2SM = (cosSqAlpha == 0) ? 0.0 :
                cosSigma - 2.0 * sinU1sinU2 / cosSqAlpha; // (18)

            double uSquared = cosSqAlpha * aSqMinusBSqOverBSq; // defn
            A = 1 + (uSquared / 16384.0) * // (3)
                (4096.0 + uSquared *
                 (-768 + uSquared * (320.0 - 175.0 * uSquared)));
            double B = (uSquared / 1024.0) * // (4)
                (256.0 + uSquared *
                 (-128.0 + uSquared * (74.0 - 47.0 * uSquared)));
            double C = (f / 16.0) *
                cosSqAlpha *
                (4.0 + f * (4.0 - 3.0 * cosSqAlpha)); // (10)
            double cos2SMSq = cos2SM * cos2SM;
            deltaSigma = B * sinSigma * // (6)
                (cos2SM + (B / 4.0) *
                 (cosSigma * (-1.0 + 2.0 * cos2SMSq) -
                  (B / 6.0) * cos2SM *
                  (-3.0 + 4.0 * sinSigma * sinSigma) *
                  (-3.0 + 4.0 * cos2SMSq)));

            lambda = L +
                (1.0 - C) * f * sinAlpha *
                (sigma + C * sinSigma *
                 (cos2SM + C * cosSigma *
                  (-1.0 + 2.0 * cos2SM * cos2SM))); // (11)

            double delta = (lambda - lambdaOrig) / lambda;
            if (Math.abs(delta) < 1.0e-12) {
                break;
            }
        }

        float distance = (float) (b * A * (sigma - deltaSigma));
        results[0] = distance;
        if (results.length > 1) {
            float initialBearing = (float) Math.atan2(cosU2 * sinLambda,
                cosU1 * sinU2 - sinU1 * cosU2 * cosLambda);
            initialBearing *= 180.0 / Math.PI;
            results[1] = initialBearing;
            if (results.length > 2) {
                float finalBearing = (float) Math.atan2(cosU1 * sinLambda,
                    -sinU1 * cosU2 + cosU1 * sinU2 * cosLambda);
                finalBearing *= 180.0 / Math.PI;
                results[2] = finalBearing;
            }
        }
    }

Answer 7

The geometry library in google maps api provide the algorithm, you can find it in the source code.

I'm not sure if google map use the same algorithm.

The algorithm is simple:

function toRadians(deg){
    return deg * (Math.PI / 180);
}

function getDistance(from, to) {
    var c = toRadians(from.lat()),
        d = toRadians(to.lat());
    return 2 * Math.asin(Math.sqrt(Math.pow(Math.sin((c - d) / 2), 2) + Math.cos(c) * Math.cos(d) * Math.pow(Math.sin((toRadians(from.lng()) - toRadians(to.lng())) / 2), 2))) * 6378137;

}

These two lines of codes would have the same result:

console.log(google.maps.geometry.spherical.computeDistanceBetween(new google.maps.LatLng(39.915, 116.404), new google.maps.LatLng(38.8871, 113.3113)));

console.log(getDistance(new google.maps.LatLng(39.915, 116.404), new google.maps.LatLng(38.8871, 113.3113)));