Batman And The CRIME !!

Batman is a savior of Gotham city. He has to save the city from the wrath of joker. So the batman asks Alfred (his tireless and faithful butler) to find a way to stop the deeds of the Joker. 

Batman wants to reach the crime scene as soon as possible from his cave. Alfred marks Joker’s probable crime scenes on Gotham's map. Whenever crime happens, Alfred receives coordinates of the scene by intercepting radio signals of Gotham Police.

Now as Batman wants to reach a crime scene as soon as possible, he asks Alfred about the shortest route to the crime scene from his cave. Now, you are Alfred and your task is to help Batman by telling him the shortest route to the crime scene.

You are given a 2D array A where A[i][0] and A[i][1] are coordinates of probable crime scene and A[i][2] is the distance between them. You are also given an array C, where each C[i] denotes the coordinate of the crime scene.

For each crime scene C[i], return the shortest distance to that coordinate from the Batman’s cave B.

It's an easy problem, right? Okay, let’s look into some examples to understand the problem better.

Example 1:

Input:

B = 0

A = [ [ 0 1 3 ]

        [ 0 3 4 ]

        [ 0 2 5 ]

        [ 3 2 3 ]

        [ 1 2 1 ] ]

C = [ 1 3 2 ]

Output:

[3 4 4]

Explanation

Let us plot the coordinates and see what we get. Now plotting these coordinates we get the following graph

We can clearly see that Batman’s cave is at 0. Now for crime scene 1 the shortest and the only distance is 3. For crime scene 3, the shortest distance is 4. Now to reach crime scene 2 we have 3 ways (0 > 1 > 2, 0 > 3 > 2, 0 > 2) with distances 4, 5, 7 respectively. Among these distances minimum is 4.

Now, how do we help Batman with this? Let’s look towards our very first approach to solve this.

Approach 1:

What we can do is, we can find all the paths from source to all other nodes and from these paths, we store the path with minimum distance. Let us find the time complexity of this approach. In the worst case the time complexity to find all the paths between two nodes is 

O(V * (V + E)) where V is number of nodes and E is number of edges.

Following this approach will make you find all the possible paths which is awesome if we have few nodes and edges. What if we have Nodes and edges in the range of let’s say 10^5 ?

Let’s look into a case to understand why this approach has high time complexity. Consider the following scenario :

Suppose we want to find the shortest distance from source (0) to destination (5), we will use strategies like BFS or DFS to find all the paths from source to destination. Clearly, we have a path (0 > 1 > 3 > 4 > 5), which is shortest, but we end up finding all other paths from source to destination in the search of minimum distance. And why are we doing so? Exactly, we are doing so because we are not certain that the path which we have found will give the minimum distance.

If we have that certainty, then we can find the shortest distance with much less effort. 

This approach will surely doesn’t work for large inputs. So what do we do now? To find an optimal solution, we always draw some observations. Let’s try to draw some.

Suppose we have a node N, a set of edges (directed from N) E = [e1, e2, e3…..] and corresponding weights of edges W = [w1, w2, w3…..]. If we sort the edges based on weights in ascending order then the edge with the minimum weight would be the shortest path to that corresponding node. For example, we have E = [1, 2, 3] and W = [3, 8, 6], now we can say that the minimum weight i.e 3, will be the minimum distance from N to the corresponding node i.e 1 in this case. In this, we are picking up the smallest distances greedily and also we are traversing the graph in BFS fashion. So here we can say that we need an algorithm which is a combination of BFS and greedy approach and here Dijkstra’s Algorithm comes to our rescue.

For code and time complexity of brute force approach refer to this github repository

Now let us look into another optimised approach.

Approach 2:

We will use Dijkstra’s algorithm to solve this problem. The algorithm is as follows:

Prerequisites

Data structures used in the algorithm are:

1. Priority Queue (min heap) (PQ) as we need an edge with minimum weight optimally.

2. An integer array named distance where distance[i] represents shortest distance of ith node from source.

3. An integer array named parent where parent[i] represents the parent of the node. Why do we have this mapping? This mapping is optional but it is good to have it because this mapping helps to trace all the shortest paths.

Approach used in the algorithm are:

1. Breadth First Search (BFS)

2. Greedy

Before applying this algorithm let us do some initialisations:

1. Initialise distance[i] to a very large value (to denote infinity). Why? Because this large value of distance[i] denotes that there is no way to reach node i from source.

Add the source node to the priority queue (PQ) (min heap) with distance = 0. Why? Because the minimum distance of the source node to itself is 0. (distance[0] = 0)

Dijkstra’s Algorithm and Time Complexity

The algorithm is as follows:

1. Since PQ is not empty, we poll the PQ and add to the distance array. Correspondingly add an entry to parent mapping. Let this polled node be n. If PQ is empty then we terminate this algorithm.

2. If distance[n] != Infinity, that means that we have already found the shortest distance for node n. Therefore we go to step 1 else go to step 3.

3. Now add all the neighbours (say B) of n to PQ with distance equal to distance[n] + nodeDistance[B].

4. After adding all the neighbours to PQ, we continue step 1. 

So easy an algorithm right? Now for better understanding see the image below. It demonstrates the algorithm in action.

Now let us say we have E number of edges and each edge is added to priority queue (min heap). The time taken by min heap to heapify when an element is added is O(logn), where n is the number of elements present in the heap. Since we are doing this for each edge we get the time complexity as O(E * log(V)), where V is the number of vertices, as there will be at most O(E) vertices in the priority queue. Which is better than the brute force approach with complexity O(V * (V + E)).

To solve the given problem, we will precompute shortest distances from source to all other nodes and then using this precomputation we can answer queries easily in O(1) time.

Let’s code this optimized approach.

For code and time complexity refer to this github repository.

So we are able to solve this problem in an optimized way. Now, let's see some applications and limitations of Dijkstra’s algorithm.

Applications:

1. It is used in Google Maps

2. It is used in finding Shortest Path.

3. It is used in geographical Maps

4. To find locations of Map which refers to vertices of a graph.

5. Distance between the location refers to edges.

6. It is used in IP routing to find the Open shortest Path First.

7. It is used in the telephone network.

Limitations:-

1.  Doing blind searches wastes a lot of time while processing.

2.  It can not handle negative edges.

3.  This leads to acyclic graphs and most often can not obtain the right shortest path.