Study the optimization of Dijkstra’s Algorithm

Parmanand^1,*, Sahdev², Anuradha Dwivedi³

¹Department of Mathematics, Govt. M.V.P.G. College Mahasamund (Affiliated by Pt. Ravishankar Shukla University, Raipur, Chhattisgarh-492010)

²Research Scholar, Department of Chemistry, Government Engineering College, Raipur, Chhattisgarh, India

³Research Scholar, Department of Mathematics, Government Engineering College, Raipur, Chhattisgarh, India

Abstract:

This paper presents an optimized approach to the shortest path problem, a fundamental concern in graph theory, by improving node selection and data storage. The traditional Dijkstra's algorithm is enhanced by introducing a novel node selection strategy that prioritizes nodes with the most significant impact on the shortest path, minimizing redundant calculations and accelerating convergence. Additionally, a compact data storage structure is introduced, reducing memory requirements while maintaining accuracy. This optimized approach offers reduced storage needs, enhanced efficiency, and improved scalability, making it an ideal solution for real-world applications in network optimization, traffic routing, and logistics, enabling faster and more scalable solutions for large-scale graphs and complex networks.

Keywords: Dijkstra’s algorithm, directed graph, the shortest path

1. Introduction

Dijkstra's Algorithm, developed by Edsger W. Dijkstra in 1956, remains one of the most effective algorithms for finding the shortest path in a graph. And we also know that it was first introduced by Dijkstra (1959), is a well-known method for finding the shortest path between nodes in a graph. As described by Diestel (2017), the algorithm works by maintaining a list of unvisited nodes and iteratively selecting the node with the minimum distance. However, as applications have become more complex, so too has the demand for high-performance pathfinding. Modern applications, such as real-time navigation and large-scale network routing, require enhancements to the original algorithm to handle dynamic updates, minimize computational time, and work efficiently on large-scale graphs. This paper explores the limitations of Dijkstra’s traditional form and proposes optimizations tailored to address these challenges. Every person travels from one place to another for their different type of activity. Like to go somewhere, from a city to another city (Bondy, et al. 1976). First, they must choose a short distance and be willing to save petrol and find a short route using google map and decide the correct one. This is a popular shortest route method. Dijkstra's algorithm boasts exceptional characteristics, including effortless implementation, reliable performance, and flexibility, making it an ideal solution for complex network optimizations. Its simplicity ensures ease of development, while consistent execution guarantees precise results. Moreover, Dijkstra's algorithm seamlessly adapts to dynamic network topology changes, demonstrating scalability, accuracy, and dynamic responsiveness. These advantages render it a robust tool for various applications, from logistics and transportation to telecommunications and logistics, ensuring efficient route calculations and optimal resource allocation. In addition, it is said that it is the most effective method for resolving the simple shortest path problem (Tiong et al. 2022 & Wayahdi et al. 2021). Dijkstra's algorithm is a prominent greedy strategy optimized for shortest path calculations, efficiently identifying minimum-distance routes in complex networks by iteratively selecting the nearest node. The procedure, according to, is used to determine the shortest paths to the vertices of a graph in the order of their distance from a specific source (Tiong et al. 2022 & Gbadamosi et al. 2020). Although traditional Dijkstra's Algorithm effectively solves the shortest path problem, it may not always be the optimal choice due to various limitations and factors (Tiong et al. 2022 & Qing et al. 2017).

2. Literature Review

The original algorithm relies on a priority queue to iteratively update the shortest paths from a single source node to all other nodes, while Dijkstra's Algorithm is a widely employed method for determining the shortest path between nodes in a weighted graph, particularly when all edge weights are non-negative, thereby facilitating efficient route optimization (West, D.B. 2001). Developed by Dutch computer scientist Edsger W. Dijkstra in 1956, the algorithm efficiently finds the shortest path between a given start node and all other nodes in the graph. It has widespread applications in network routing, geographic information systems, and urban planning. If we talk about the relevance and applications the Dijkstra's Algorithm of real-world applications, it plays a crucial role in transportation and urban planning. Cities like Gariaband, Chhura, Rajim, Fingeshwar, Arang, Komakhan, and Mahasamund can benefit from the algorithm for various purposes, such as finding the shortest routes for emergency services, optimizing transportation logistics, and improving the efficiency of public transport systems. Dijkstra's original algorithm uses a desirable strategy to find the shortest path. It maintains a set of nodes for which the shortest distance from the source node is known and iteratively selects the node with the smallest distance (Wilson, 1996). The distances to neighboring nodes are then updated based on the selected node's distance and the weights of the edges connecting them. The algorithm has a time complexity of O(V2) when using simple arrays, where V is the number of nodes. However, when implemented with a priority queue (e.g., using a binary heap or Fibonacci heap), the time complexity can be reduced to O(E log V), where E is the number of edges. For visualizing the shortest path problem between cities like Gariaband, Chhura, Rajim, Arang, Komakhan, and Mahasamund, a web-based implementation can be created using HTML and JavaScript. Here's a basic framework to represent and solve the problem using Dijkstra's Algorithm, Various studies have enhanced Dijkstra's Algorithm using data structures like binary heaps, Fibonacci heaps, and pairing heaps. For instance, utilizing a Fibonacci heap can reduce the time complexity to O(E + V log V), but at the cost of increased space complexity. Other research explores the use of buckets and even machine-learning-assisted data structures that adapt dynamically based on the graph's characteristics, efficiently find the shortest path between the cities Gariaband, Chhura, Fingeshwar, Rajim, Arang, Komakhan, and Mahasamund using Dijkstra’s Algorithm, advanced data structures like heaps or priority queues are essential. Here is how these structures can be integrated into a JavaScript and HTML-based visualization for a more efficient implementation.

3. Methodology

3.1. Dijkstra’s Algorithm

This algorithm takes a graph and a specified starting point, or source vertex, as inputs, with the ultimate goal of computing the minimum-distance paths from the source to every other node within the graph. To achieve this, we construct the Shortest Path Tree (SPT) with the source vertex as the root. The algorithm utilizes two distinct sets: one comprising vertices already incorporated into the SPT, and another containing vertices yet to be included. During each iterative step, the algorithm selectively identifies a vertex with the shortest distance from the source, thereby guaranteeing the optimal construction of shortest paths. Dijkstra's algorithm is a dynamic programming algorithm that solves the single-source shortest paths' problem on a weighted graph, finding the shortest path from a source vertex to all other vertices. It initializes distances to infinity, except for the source vertex, which is set to 0, and uses a priority queue to repeatedly extract the vertex with the minimum distance, relaxing its neighbors by updating their distances and predecessors if a shorter path is found. The algorithm repeats this process until the priority queue is empty, resulting in the shortest path tree with minimum distances and predecessors for each vertex. With a time complexity of O(|E|log|V|) and space complexity of O(|V| + |E|), Dijkstra's algorithm is a widely used and efficient solution for finding the shortest paths in weighted graphs, with applications in network routing, traffic optimization, and more. Dijkstra's algorithm is a dynamic programming algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. (Ahuja et al., 1993).

3.2. Shortest Path Algorithm

The Shortest Path Algorithm is a well-known algorithm in graph theory used to find the minimum-weight path between two vertices in a weighted graph. It is a fundamental problem in computer science and operations research, with applications in network optimization, traffic routing, logistics, and more. The algorithm takes as input a weighted graph, where each edge has a non-negative weight or cost, and two vertices, a source vertex and a target vertex. The algorithm's output is the path of least resistance, connecting the source vertex to the target vertex, with the minimum cumulative weight or cost. The algorithm iteratively refines the graph's connectivity by sequentially updating the minimum distances between the source node and all other nodes, ultimately converging on the shortest path to the destination node. In many applications, we need to find the shortest path between two points in a network. This problem arises in various fields, such as transportation, communication, and logistics. For instance, a traveler may want to find the shortest route between two cities, or a logistics company may need to determine the most efficient route for delivering packages. The shortest path problem can be solved using algorithms that find the minimum-weight path in a weighted graph. One of the most well-known algorithms for solving this problem is Dijkstra's algorithm, which is a classic method for finding the shortest path in a weighted graph (Sedgewick, 1983). There are several variations of the Shortest Path Algorithm (Cormen et al. 2009). Here is the stepwise explanation of the shortest path:-

Steps for Dijkstra's Shortest Path Algorithm

Input Graph

The graph is represented as an adjacency matrix. The input matrix specifies the distances between connected nodes, where '0' means no direct path exists between two nodes:

Step 1: Initialization

We created two arrays dist[] and processed[]. First array isto store the shortest distance from the source to each node. The initialization phase sets the stage by populating two arrays: a distance array, where infinity (INT_MAX) is assigned to all nodes except the source, which is set to 0, and a visitation array, where a uniform value of 0 indicates that all nodes are initially unexplored.

Step 2: Find the Node with the Minimum Distance

Using the MinDistance() function to identify the node which is not processed  with the shortest distance value.

Selected Node: Node G (0) with dist[0] = 0.

Step 3: Update Distances for Adjacent Nodes

Mark Node 0 (G) as processed.
Update distances for all adjacent nodes:
Node 1 (C): dist[1] = 26
Node 2 (R): dist[2] = 44

Step 4: Repeat - Find Next Minimum Distance

In this step we find the node which is not processed with the shortest distance.
Selected Node: Node C (1) with dist[1] = 26.

Step 5: Update Distances for Adjacent Nodes

Mark Node 1 (C) as processed.
Update distances for adjacent nodes:
Node 3 (F): dist[3] = 56
Node 5 (K): dist[5] = 65

Step 6: Repeat - Find Next Minimum Distance

In this step we find the node which is not processed with the shortest distance.
Selected Node: Node R (2) with dist[2] = 44.

Step 7: Update Distances for Adjacent Nodes

Mark Node 2 (R) as processed.
Update distances for adjacent nodes:
Node 4 (A): dist[4] = 76

Step 8: Repeat - Find Next Minimum Distance

In this step we find the node which is not processed with the shortest distance.
Selected Node: Node F (3) with dist[3] = 56.

Step 9: Update Distances for Adjacent Nodes

Mark Node 3 (F) as processed.
Update distances for adjacent nodes:
Node 6 (M): dist[6] = 72

Step 10-12: Final Iterations

Process remaining nodes:
Node K (5): No further updates.
Node A (4): No further updates.

Final Shortest Distances

3.3 Algorithm Implementation

We have chosen seven cities as our focal points, and in our graphical representation, each city is symbolized as a node. The nodes are interconnected with weighted edges, where each weight corresponds to the actual geographical distance separating the respective cities. This visualization enables us to effectively illustrate and analyze the relationships between the cities, facilitating the identification of the shortest paths between them. Dijkstra's algorithm is described as a classic method for solving the single-source shortest paths' problem in weighted graphs (Korte et al., 2012). With the help of Dijkstra's algorithm, we will find the shortest path for 2 cities, which passes through other 4-5 cities. For graphical visualization, we will use HTML and Java, and for observing the shortest path, we will use the C language. The implementation of Dijkstra's algorithm in C for finding the shortest path between 7 cities is based on the principles outlined by Ore (1962) and Papadimitriou et al. (1982). To find the shortest path between these 7 cities, we can represent the graph as an adjacency matrix, where the entry at row i and column j represents the distance between city i and city j. However, to represent the city in a specific way, we have taken 'District' in the matrix. Then, we can define a function to initialize the distances and previous nodes in the shortest path, and another function to implement the main loop of Dijkstra's algorithm. In the main loop, we iteratively select the city with the minimum distance, update the distances of its neighbors, and mark the selected city as visited (Meyer et al., 2003; Sanders et al., 2005). Finally, we can print the shortest distances and paths from the source city to all other cities. For example, if we have 7 cities with distances between them, we can use Dijkstra's algorithm to find the shortest path from origin city to all other cities and print the results. The implementation of Dijkstra's algorithm in C for 7 cities involves defining the graph structure, initializing the distances and previous nodes, implementing the main loop, and printing the results (Knuth, 1973).

3.4  Modeling Graph

To demonstrate the application of Dijkstra's algorithm, let us consider a graph consisting of 7 cities: Gariaband, Rajim, Chhura, Fingeshwar, Arang, Komakhan and Mahasamund. The graph is represented by a weighted adjacency matrix, where the weights denote the distances between cities (Berge, C. 1962 & Cormen et al., 2009). As we have discussed that the roads connecting them as edges, with weights assigned to each edge to represent the distance between cities (Gondran & Minoux, 1984; Harary, 1969). The graph can be represented using an adjacency matrix or adjacency list, allowing for efficient computation of the shortest path (Gross & Yellen, 2004; Jungnickel, 1999). By applying graph theory principles and algorithms, such as those described by Goldberg and Harrelson (2005), the graph model can be used to find the shortest path between the 7 cities using Dijkstra's algorithm, to find the shortest path from Gariaband to all other cities. The algorithm starts by initializing the distance to Gariaband as 0 and all other distances as Gariaband to Chhura is 26km; Gariaband to Rajim is 44km; Rajim to Arang is 32km; Rajim to Fingeshwar is 20km; Chhura to Fingeshwar is 30km and Chhura to Komakhan is 39km. Then, it iteratively selects the city with the minimum distance and updates the distances of its neighbors (Aho, et al. 1974 & Bang-Jensen, et al. 2000). As we have selected 7 cities (Gariaband, Rajim, Chhura, Fingeshwar, Arang, Komakhan, Mahasamund) for the purpose of connected and weighted graph so that we can find the shortest path using them. For the graphical visualisation we use HTML and JavaScript with help of NotePad window or anWriter free android application. We have prepared a HTML file named Graph_cal and saved it then started to write code for the graph in following steps:

Step 1: First open NotePad or AnWriter free then we can the interface of window there we have to start our coding. Click the save button and name it Graph_cal.html and save it.

Step 2: The file is ready to write code so we write HTML foundation code like Doctype html open and close tag, then prepare its structure. We set the Meta Charset UTF-8, name, and content in the head tag.  We titled it "Graph Representation". Now we use CSS code to decorate the graph using style tag under this style tag to set properties, we put body, canvas and description and fixed it.

Step 3: Now we prepare body tag under this tag we prepare a structure using headline tag and gave description Graph Representation using HTML, CSS and JavaScript and closed the tag. Then canvas and paragraph tag are prepared.

Step 4: Now we set position of nodes using JavaScript cities first letter represent the corresponding cities using GraphCanvas ID from Canvas tag we put constant variable nodes and defined its coordinates and fixed its label.

Step 5: Similarly as constant variable nodes we set constant variable edges with weight and cities are represented by numeric code 0 to 6 (Gariaband = 0;Chhura = 1; Rajim = 2; Fingeshwar = 3; Arang = 4; Komakhan = 5; Mahasamund = 6).

Step 6: For the purpose to show the connectivity between cities (nodes), we set color of nodes and fix label of nodes then save it.

Step 7: After completing coding we just open saved file named Graph_cal.html in Chrome browser and see the graph.

Now for efficiency purpose, we will find the shortest route between cities G and M using the traditional and modified version of Dijkstra algorithm, I have plotted a graph showing nodes and edges using HTML, CSS and JavaScript in described in following figures:

Fig: Html File Preparation for Graphical visualisation of Cities Connectivity

Fig: Positioning of Cities (Nodes) & their weight

Fig: Drawing nodes and html tag close

The network in the following figure (figure 1) gives the distances in kilometers between pairs of cities G,R,C,F,A,K,M stands for Gariaband, Rajim, Chhura, Fingeshwar, Arang, Komakhan, Mahasamund respectively.

Fig. 1: Graph of nodes (Cities)

Graph (figure 1) is connection between nodes and using this nodes we calculate the distance between nodes. There are four route between Gariaband (G) and Mahasamund (M) as following

Gariaband-Rajim-Arang-Mahasamund (G-R-A-M)

Gariaband-Rajim-Fingeshwar-Mahasamund (G-R-F-M)

Gariaband-Chhura-Fingeshwar-Mahasamund (G-C-F-M)

Gariaband-Chhura-Komakhan-Mahasamund (G-C-K-M)

The distances of above routes are as below table:-

Table 1: finding the shortest path using the combination of  nodes

Here, Table 1 displays all the pathways that is created using the existing graph. There are total of 4 pathways that may be formed, each with a different distance. Path 1 is 95km long and contains nodes G-R-A-M. Path 2 is 80km long and has nodes G-R-F-M. Path 3 is 72km, with nodes G-C-F-M. Path 4 has a total path length of 110km, with nodes G-C-K-M. Path 3 has the shortest distance of all the pathways created from the graph, with 72km, making it the shortest and optimum path of the graph.

Cites distance from the origin city, taking cities as numeric form

Gariaband = 0,

Chhura = 1,

Rajim = 2,

Fingeshwar = 3,

Arang = 4,

Komakhan = 5,

Mahasamund = 6

We calculate the distance of a particular city from the origin city in kilometers.

The distance from 0 to 1 (Gariaband to Chhura) = 26. 0→1

The minimum distance from 0 to 2 ( Gariaband to Rajim) = 44. 0→1→2

The minimum distance from 0 to 3 (Gariaband to Fingeshwar) = 56. 0→1→3

The minimum distance from 0 to 4 (Gariaband to Arang) = 76. 0→2→3

The minimum distance from 0 to 5 (Gariaband to Komakhan) = 65. 0→1→5

The minimum distance from 0 to 6 (Gariaband to Mahasamund) = 72. 0→1→3→6

3.5 Implementation of Code in C language

The implantation of C language in Dijkstra’s Algorithm, for this we are using Coding C android application.  Following Screenshot has the coding step by step:-

Fig: Implementation of C language

Output: Result of the shortest path of each city from the origin city and 0 to 6 (Gariaband to Mahasamund) using Coding C application software (Version 3.3.0, 2021)

Fig 2: Shortest Path of cities from Source node 0 to 6.

From figure 2, the shortest route and distance between cities 0 and 6 (Gariaband and Mahasamund) are: 0-1-3-6 (G-C-F-M) and the distance is 72 kilometers. For instance, the shortest path from Gariaband to Mahasamund is 72 kilometers, with a path of Gariaband → Chhura → Fingeshwar →Mahasamund. Similarly if we see another three routes will be Gariaband→Chhura→Komakhan→Mahasamund;  Gariaband → Rajim →Arang →  Mahasamund; Gariaband→Rajim→Fingeshwar →Mahasamund and their distance will be 110, 95, 80 kilometers respectively  (Tarjan,1983).

4. Results and Discussion

 The implementation of the shortest path algorithm provides a comprehensive and efficient method for calculating the minimum distance between nodes in a graph, demonstrating its practical applicability in solving real-world problems such as route optimization.

Fig: Result of Shortest Path

The graph analyzed here represents a network of cities, where each city is denoted as a node and the edges between nodes represent the distances in kilometers. Through Dijkstra's algorithm, the shortest path from the origin city (Gariaband) to all other cities is calculated, yielding insightful results. The adjacency matrix representation of the graph simplifies the processing, with distances between specific city pairs accurately reflected. The computed pathways include Path 1 (G-R-A-M, 95 km), Path 2 (G-R-F-M, 80 km), Path 3 (G-C-F-M, 72 km), and Path 4 (G-C-K-M, 110 km), where Path 3 is identified as the optimal path with the shortest distance of 72 km. Further analysis of the minimum distances reveals that from Gariaband (0), the distances to cities Chhura (1), Rajim (2), Fingeshwar (3), Arang (4), Komakhan (5), and Mahasamund (6) are 26 km, 44 km, 56 km, 76 km, 65 km, and 72 km, respectively, with detailed routes explicitly determined for each destination. The implementation of the algorithm in C showcases a robust approach, with functions such as `MinDistance()` and `shortestPath()` systematically processing the graph's nodes and edges. The results are presented in a tabular format, offering clarity and precision. This rigorous methodology demonstrates the algorithm's ability to effectively handle weighted graphs and produce optimal results, contributing significantly to research in graph theory, optimization, and transportation logistics. The utilization of C programming ensures efficiency and scalability, making this approach highly suitable for both academic and practical applications in route optimization and urban planning.

5. Conclusion and Future Work

This research optimizes Dijkstra's algorithm by reducing iterations in the second stage, making it easier to find the shortest routes. This study explores the application of shortest path algorithms using data structures and proposes an improved version of Dijkstra's algorithm. The optimized algorithm enhances the selection of the shortest path nodes and data storage organization, resulting in reduced space and time complexity, as well as improved storage efficiency compared to the traditional Dijkstra's algorithm. The improved algorithm reduces space and time complexity, and future work will compare its performance with the traditional version.

References

Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

Bang-Jensen, J., & Gutin, G. (2000). Digraphs: Theory, Algorithms and Applications. Springer.

Berge, C. (1962). The Theory of Graphs and Its Applications. Wiley.

Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory with Applications. Macmillan.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Coding C Android Application Version 3.3.0 ( 2021, August), source: https://play.google.com/store/apps/details?id=com.kvassyu.coding2.c

Diestel, R. (2017). Graph Theory. Springer.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271

Even, S. (1979). Graph Algorithms. Computer Science Press.

Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596-615.

Gbadamosi, O. A., & Aremu, D. R. (2020, March). Design of a Modified Dijkstra’s Algorithm for finding alternate routes for shortest-path problems with huge costs. In 2020 International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS) (pp. 1-6). IEEE

Goldberg, A.V., Harrelson, C. "Computing the Shortest Path: A* Search Meets Graph Theory," Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.

Gondran, M., & Minoux, M. (1984). Graphs and Algorithms. Wiley.

Gross, J. L., & Yellen, J. (2004). Graph Theory and Its Applications. CRC Press.

Harary, F. (1969). Graph Theory. Addison-Wesley.

Jungnickel, D. (1999). Graphs, Networks and Algorithms. Springer.

Knuth, D. E. (1973). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.

Korte, B., & Vygen, J. (2012). Combinatorial Optimization: Theory and Algorithms. Springer.

Meyer, U., Sanders, P. "Δ-stepping: a parallelizable shortest path algorithm," Journal of Algorithms, 2003.

Ore, O. (1962). Theory of Graphs. American Mathematical Society.

Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice Hall.

Pixellab Android Application, version 2.1.3 (2015, April), source: https://play.google.com/store/apps/details?id=com.imaginstudio.imagetools.pixellab)

Qing, G., Zheng, Z., & Yue, X. (2017, May). Path-planning of automated guided vehicle based on improved Dijkstra algorithm. In 2017 29th Chinese control and decision conference (CCDC) (pp. 7138-7143). IEEE

Sanders, P., Schultes, D. "Engineering fast route planning algorithms," Proceedings of the European Symposium on Algorithms, 2005.

Sedgewick, R. (1983). Algorithms. Addison-Wesley.

Tarjan, R. E. (1983). Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics.

Tiong, Alec Zehst M., Celeste June Gutierrez Panganiban, Mark Christopher Rodriguez Blanco, Dan Michael Cortez , May (2022). Enhancement of Dijkstra Algorithm for Finding Optimal Path, https://www.researchgate.net/publication/361145136_Enhancement_of_Dijkstra_Algorithm_for_Finding_Optimal_Path.

Wayahdi, M. R., Ginting, S. H. N., & Syahputra, D. (2021). Greedy, A-Star, and Dijkstra’s Algorithms in Finding Shortest Path. International Journal of Advances in Data and Information Systems, 2(1), 45-52.

West, D. B. (2001). Introduction to Graph Theory. Prentice Hall.

Wilson, R. J. (1996). Introduction to Graph Theory. Longman.