The Algorithm that facilitates Google Maps

Google Maps X Shortest Route feature

There’s been a lot of times when we have switched between routes and tried to figure out the shortest route with minimum traffic while using Google Maps. Ever Wondered How Google Maps makes it work?. Well, it’s a very crucial problem to solve. We have “n” number of possible routes from our current location to our destination and to figure out the shortest one amongst them with the least time complexity (that is in no time moreover on a real-time basis) is extremely bizarre right. But don’t worry Dijkstra Algorithm has got it all. Although there are plenty of shortest pathfinding algorithms that are more advance and more accurate under certain cases but still, Dijkstra’s algorithm holds its real-world significance.

Dijkstra algorithm was given by a Dutch Computer scientist, Edsger W. Dijkstra back in 1956 and was published 3 years later. This algorithm aims to find the shortest path in a directed or undirected graph with non-negative edge weights.

In a graph for a given particular source node, the algorithm accurately finds the shortest path between that node and every other node. Also used for finding the shortest path between a single node to a single destination and once the path with the minimum cost is obtained we stop the further proceedings.

Let’s stress on the problem which is solved by Dijkstra Algorithm suppose if we are running late for work and we open up Google Maps to search for the shortest and the fastest route to our destination. There are chances that there is congestion on some routes and maybe the shortest route has high congestion how to tackle all these scenarios. Well, the Dijkstra algorithm considers your current location and your destination as a node/vertex and considers all the possible paths as edges between them, and the congestion in those routes is depicted by the weights attached to those edges.

We can imagine the shortest distance problem as a graph with (Destination as) vertices and (Distance) as edges.

Dijkstra Algorithm has a high significance because of its applicability in Real-World Scenarios

• Digital Mapping Services in Google Maps — Finding the shortest routes
• Social Networking Applications — People who you may know (Functionality)
• Telephone Network
• IP routing to find Open shortest Path First — it is widely used in IS-IS routing protocol and OSPF routing protocol
• Flighting Agenda — Flight arrival time scheduling and flight bookings etc
• Robotic Path — Robots that are used to deliver packages from one place to another use this algorithm.

Shortest Route Graph problem

Approach — Dijkstra works on the Greedy Technique it picks the best immediate output but does not consider the overall case, hence it is considered greedy it opts for the best optimal solution at each small stage. Dijkstra uses a method called “Edge Relaxation” for each selected/source vertex.

u=source vertex/selected vertex

v = destination vertex

d[] = distance array that stores the distance of all vertices

c(u,v) = cost of the edge between vertices u and v

Code

// If thesum of distance of source vertex and the cost of the edge between the source vertex and destination vertex (d[u] + c(u,v)) is less than the distance of the destination vertex (d[v]).

If ( d[u] + c(u,v) < d[v] )

// Then we change the value of the destination vertex by the sum.

d[v]=d[u]+c(u,v)

Let’s Get started with the working of the Dijkstra Algorithm. We take an example of a weighted, directed, and single source vertex graph.

Consider this graph

Here S is the source vertex

Step 1: Source vertex is “S” with the weight 0, we create two sets

Visited nodes ={} and

Unvisited Nodes ={S,a,b,c,d,e}

Step 2: Choose the vertex S since it is the source vertex

Visited nodes ={S} and

Unvisited Nodes ={a,b,c,d,e}

Step 3: We check the distance of all the vertices from the vertices S. And we will relax all the outgoing edges from the source vertex. We will make the distance of all vertex which are not outgoing from the source vertex as infinty. Since there exist no direct edge to them from the source vertex.

Step 4: We Choose the vertex with the shortest distance(refer to the table above). We see vertex a has the minimum value i.e. 1.

We relax all the outgoing edges from a. That is we relax vertexes b,c,d

Visited nodes ={S,a} and

Unvisited Nodes ={b,c,d,e}

Step 5: Repeat the steps and find the vertex with minimum distance and then select it. We will not consider the verses that have already been chosen.

We will select vertex d with a distance value of 2.

Visited nodes ={S,a,d} and

Unvisited Nodes ={b,c,e}

Vertex d has only 1 directed vertex i.e vertex e and after relaxation of vertex e we get the new value as 2+2=4.

Step 6: we will choose the vertex with minimum weight I.e b~3, it has only one directed edge to vertex d and since vertex d is already released we need not relax it again.

Visited nodes ={S,a,d,b} and

Unvisited Nodes ={c,e}

d[b] + 2 = 3 + 2 = 5 > 2 , also if we try to relax it we notice no changes will be made since d already has a better minimum distance.

Step 7: Vertex c is chosen as it has the next shortest distance. The outgoing edges of vertex ‘c’ are relaxed.

Visited nodes ={S,a,d,b,c}

Unvisited Nodes ={e}

Step 8: Vetex ‘e’ is chosen since it is the shortest one left. There is no outgoing edge from e hence we leave it like that.

Visited nodes ={S,a,d,b,c,e} and

Unvisited Nodes ={}

Finally the shortest path is obtained in the order S-a-d-b-c-e

So that was the crux of the Dijkstra Algorithm.

The complexity of Dijkstra using the adjacency list is O(V²) (V is the number of vertices). But if we use a Min-priority queue the complexity is significantly reduced to O( V+E log V). When we use Min-priority queue we go for a BFS or a Breadth-First Search.

Not everything with the Dijkstra algorithm works fine. For example when we have a negative edge Dijkstra algorithm may or may not give a substantial result. Therefore Dijkstra Algorithm fails to detect negative edges and negative cycles and a refined version of the Dijkstra Algorithm to work on negative edges is the Bellman-Ford. Bellman-Ford algorithm is somewhat refined and it gives the correct results in a graph with negative edges but it fails in the case where negative cycles are involved. Dijkstra may or may not give the correct result with Negative edges/cycles and Bellman-ford give correct result in case of negative edges and fails in negative cycles case, but when both of these algorithms are merged it is possible to tackle negative weight edges(to remove negative edges and detect negative cycles), such an algorithm is called Johnson’s algorithm.

We always