Determination of shortest path using Dijkstra’s algorithm & Kruskal’s algorithm

I have been working on a project for quite some time now. The aim of the project is to find ways to reduce fuel consumption in vehicles.

In order to do the project, I had gone through many information sources. I found out that the primary way of less fuel consumption is to use the shortest path to reach a place. There were other options as well.

Now the primary question rising in my mind was how we could know the shortest path between two places. After reading many articles, I came across quite a few solutions.

The most common solution was   avoiding of crowded Streets. Other solutions included sort of trial and error methods. Whatever the solution was there would be fuel expenditure.

SoI decided to find it out myself. There is a huge number of delivery men plying across a city daily. It would help them the most.

In this IA, I have decided to calculate the shortest path for a delivery executive connecting all the delivery locations in the same city using Dijkstra's Algorithm.

The main motive of this IA is to find the shortest path a delivery executive must obtain to deliver all the assigned products at respective locations at optimum use of fuel. Another motive of this IA is to find the efficiency of Dijkstra’s Algorithm and Kruskal’s Algorithm in predicting the shortest path between any two location in a weighted graph.

What should be the shortest path for a delivery executive connecting all the delivery locations in the same city?

Shortest path between any two location is very essential concept not only in daily life but also in machine learning. In this IA, we will concise our studies within one of the applications of determination of shortest path which we see in daily life. Every navigation app and software use these techniques to predict the shortest path between the source and the destination.

Ideally, determination of shortest path is actually a minimization problem which further falls under the domain of optimization. In optimization, Greedy method is one of the most important tools used in optimization problems. According to Greedy method, an optimization problem should be solved in stages by taking one step at a time and considering one input at a time. In Greedy method, there are several procedures which are followed to solve optimization problem. Dijkstra’s Algorithm is one of such procedures of Greedy method which is very efficient in determining shortest path between any two points. Usually, Dijkstra’s algorithm is used to find the shortest path in a weighted graph connecting several points. Moreover, minimal spanning tree from a weighted graph can be found using Kruskal’s Algorithm. In this IA, we will firstly design a weighted graph from the required data of several paths between the source and the destination. After that we will use Dijkstra’s Algorithm and Kruskal’s Algorithm to determine the shortest path between the source and the destination and compare the results and efficiency of the algorithm.

The steps of this Algorithm are shown below:

Let us consider a point in the Graph from which we are starting be the initial point (node) and the point in the graph at which will be the destination be the ending point (node).

The steps of this Algorithm are shown below:

• We mark all the nodes which are unvisited and prepare a set of all unvisited nodes which is called the unvisited set.
• We assign an approximate distance value to every node such that the initial node is set to zero and all the other nodes are set to infinity. The initial node is marked the current one.
• We calculate the approximate distances of the unvisited neighbours through the current node by considering each of them at a time. The approximate newly calculated distance is compared to the current assigned value and the smaller one is assigned. For instance, if 6 is the current marked distance of A, and 2 is the length of the edge connecting it to a neighbour point B, then 6 + 2 = 8 will be the distance to B through A. We change the distance to 8 if the distance was previously a value greater than 8. We keep the current value otherwise
• We mark the current node as visited and remove it from the unvisited set once we finish considering all the unvisited nodes of the current node. We never check a visited node again.
• We stop if the destination node has been marked as visited(when a route is planned between two definite nodes) or if infinity is the smallest approximate distance between the nodes in the unvisited set (when a complete traversal is planned; occurs when the initial and remaining unvisited nodes do not have any connection). This finishes the algorithm.
• We otherwise set the current node as the unvisited node with the smallest approximate distance, and we return to the third step.

When we plan a route, it is not required to wait unless the destination node is "visited" as above: we can stop the algorithm when the destination node has the smallest approximate distance amongst all other "unvisited" nodes (and hence would be chosen as the next "current").

The steps of this Algorithm are shown below:

Let us consider a point in the Graph from which we are starting be the initial point (node) and the point in the graph at which will be the destination be the ending point (node).

The steps of this Algorithm are shown below:

• Arrange all the weights between the nodes in an ascending order.
• Draw the nodes in the same order.
• If any node is making a loop, then that loops should be avoided.

In Figure 2, we have constructed a weighted graph which comprise the route connecting 25 nodes. Using Dijkstra’s Algorithm, I will find the shortest path between Bandra West and Colaba.  I will be denote every place using a variable as follows:

Sample Calculation:

Distance between nodes A and B is 2.6 units.

Furthermore, distance between nodes B and C is 2.6 units. So the total distance from nodes A to C is 5.2 (= 2.6 + 2.6) km.

Likewise, the subsequent minimum tentative distances between nodes are added to the previous distances and we finally obtain the required values.

So, from the table, we can state that the shortest distance between Bandra West and Colaba is 23.7Km

The nodes are represented in the same way as shown in the previous case.

According to the algorithm, first of all, we have to arrange all the weights between the nodes in an ascending order.

Now, the distance between Bandra West and Colaba will be found using the graph that is formed using Kruskal’s Algorithm. It is clear from the Graph that, only one route is possible between the above-mentioned source and destination. The path will comprise the nodes in the following order:

A→B→C→D→F→G→I→L→P→Q→U→W→X→Y

In order to follow this route, the distance between Bandra West (Source) and Colaba (Destination) shown below:

Distance = 2.6 + 2.6 + 1.8 + 0.8 + 1.2 + 3 + 2.8 + 2.4 + 2.3 + 1.8 + 1.3 + 2.4 + 1.2 = 26.2 Km

In this IA we have found that the shortest path that can be taken by a delivery executive among multiple delivery routes, can be calculated using Dijkstra’s Algorithm. To do a comparative analysis, we have also find the route between the same source and destination using Kruskal’s Algorithm also. We have found that the routes can be mapped in terms of a weighted graph made up of nodes. Firstly, using Dijkstra’s Algorithm, we have found the distance between Bandra West (Source) and Colaba (destination) is 23.7 Km. This deduction will make the movement of both delivery executives and the general people, more economical and easier.

Moreover, we have found the route between the same source and destination, i.e., from Bandra West to Colaba using Kruskal’s Algorithm. Using this method, we have concluded that, the distance between the source and the destination has come out to be 26.2 Km.

From the above study, we can say that, Dijkstra’s Algorithm is more efficient in finding the shortest path between any two nodes in a weighted graph. On the other hand, Kruskal’s Algorithm is efficient in finding a route that will connect all the nodes present in the graph but the distance between source and the destination might not be the shortest.

In a nutshell, Dijkstra’s Algorithm is more efficient in finding the shortest path between any two routes thus providing the delivery executing with a route that will require minimum amount of fuel to be covered decreasing his cost on fuel.

• Ruiz, Rubén, and Thomas Stützle. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem." European Journal of Operational Research 177.3 (2007): 2033-2049.
• Deng, Yong, et al. "Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment." Applied Soft Computing 12.3 (2012): 1231-1237.
• Graham, Ronald L., and Pavol Hell. "On the history of the minimum spanning tree problem." Annals of the History of Computing 7.1 (1985): 43-57.
• Johnson, Donald B. "A note on Dijkstra's shortest path algorithm." Journal of the ACM (JACM) 20.3 (1973): 385-388.
• Greenberg, Harvey J. "Greedy algorithms for minimum spanning tree." University of Colorado at Denver (1998).
• https://www.google.com/maps