Dijkstra’s and A* Algorithms

As a robotics enthusiastic undergraduate, I am familiar with some algorithms used to solve mazes, by following either lines or walls. But when I think about real-world applications, the first thing that comes to my mind is Google maps. We use this app more often in our day to day life and it always leads us to our desired destination. It not only considers the shortest path but also always tries to avoid the busy roots too. So, I dig some deeper to find the algorithms behind this app that how it sort out the quickest path. I found that Dijkstra’s and A* algorithms are some of them which helped google maps to improve its technology. First I will guide you through Dijkstra’s algorithm using the below map.

Map

Suppose that the S node is the starting location and the Z node represents the destination. The numbers on the node connecting lines(edges) are the weight of those routes. These values represent the traffic on that route.

Dijkstra’s Algorithm

Our intention is to find the quickest path to the destination. Following the below rules will help to understand this algorithm.

• The node should be represented in two letters. The first letter is the current node and the second letter is the node that we came from.
• Update an array with the node and the sum of weights.
• The array must update in the ascending order of weights.

Step 1

{S:0; BS:2; LS:3; AS:7}

First, we select the current location(S) and then we update the array by considering all the possible nodes that we can go from node S. There are three paths that we can think of being the best path to our destination. After completing the node S, we can add it to a list.

closed_nodes=[S]

Step 2

Then we should select B, as it has the next minimum cost.

{S:0; BS:2; LS:3; CB:5; AB:5}

From node B, we can choose either A or C. So, we can update C but node A is almost there. We can come to node A from either B or S, but coming through the node B is much easier when we compare the sum of weights. So, we change AS into AB and the weight too. In the end, we can update the list by adding a BS.

closed_nodes=[S, BS]

Step 3

{S:0; BS:2; LS:3; CB:5; AB:5; ML:8}

The next node is L and it leads us to only node M. The list should update with node L.

closed_nodes=[S, BS, LS]

Step 4

{S:0; BS:2; LS:3; CB:5; AB:5; DC:7; ML:8}

The next node is C. As you can see, there are two paths available from that node. Node D can add to the array easily but there is another path to node A. So, we can think of updating the array by updating CB into CA. But in any case, we do not update the node that we consider in each step.

The list should update with the C node.

closed_nodes=[S, BS, LS, CB]

Step 5

{S:0; BS:2; LS:3; CB:5; AB:5; DC:7; ML:8}

The next node is A and there is not any other new way that node A can lead us to. So, it seems like node A is a dead end. So, we have to skip this step without updating the list.

closed_nodes=[S, BS, LS, CB]

Step 6

{S:0; BS:2; LS:3; CB:5; AB:5; DC:7; ML:8; ZD:9}

After this step, we come to our destination but the is the node M before Z. In this case, it will not make any difference by considering node M, but we need to consider node M in our next step to achieve our goal. Before that, we have to update the list.

closed_nodes=[S, BS, LS, CB, DC]

Step 7

{S:0; BS:2; LS:3; CB:5; AB:5; DC:7; ML:8; ZD:9; OM:12; NM:12}

closed_nodes=[S, BS, LS, CB, DC, ML]

Array and the list are updated as we discuss in the above step.

Step 8

{S:0; BS:2; LS:3; CB:5; AB:5; DC:7; ML:8; ZD:9; OM:12; NM:12}

The next node is the destination and it should be added to the list too.

closed_nodes=[S, BS, LS, CB, DC, ML, ZD]

Step 9

This is the last step of this algorithm. From the beginning, the list was updated because it helps to interconnect all the nodes from the starting point to the destination. So, the path is, ZD->DC->CB->BS->S.

Answer: S->B->C->D->Z

The problem in Dijkstra’s Algorithm

This algorithm finally brings the best path but there is a problem that we did not catch in this example.

According to the above example, we need to find the quickest path that we can arrive at our destination. When we come from node S to A, it seems like there is not any path if we chose nodes L, M, N. As mentioned earlier, this algorithm always tries to consider the lower weighted path first. So, it gives the correct answer but wastes more computational time by considering only the weights. Because this algorithm does not have any idea of the direction of the destination.

A* Algorithm

A* algorithm gives a solution to the problem in Dijkstra’s algorithm by considering the sum of weights and the displacement from the starting point. In each step, the array should be updated by the sum of weights and displacement. Sometimes A* algorithm can solve faster than Dijkstra’s algorithm because it always knows where it is heading on.

Note: The weights or displacements can not be negative, because it will not work if this exception was not handled.