2026· International journal of research and scientific innovation· Vol 13, pp. 5348-5358· 0 citations
TL;DR
Comparative analysis against A* search Algorithm, ALT, ALT (A* search Landmarks and Triangle inequality), and Arc Flags algorithms demonstrated that Dijkstra consistently achieved faster computation times, lower memory overhead, and higher accuracy in path selection, resulting in significant reductions in delivery and planning time.
Abstract
Route optimization is a critical component in transportation, logistics, and network systems, where efficiency directly impacts cost, time, and resource utilization. Among shortest path algorithms, Dijkstra’s algorithm remains a cornerstone due to its ability to compute optimal routes in weighted graphs with non-negative edge costs. This study evaluates the importance of Dijkstra’s algorithm in route optimization by combining theoretical analysis with empirical experimentation. A well-defined experimental framework was established using standardized datasets, including DIMACS road network benchmarks and OpenStreetMap (OSM) regional extracts, to ensure reproducibility and comparability. Graph types were clearly specified: sparse graphs representing rural networks, dense graphs modeling urban transportation systems, and multi-criteria weighted graphs incorporating distance, travel time, and congestion factors. Experiments were conducted in a controlled computational environment comprising an Intel Xeon CPU, 32GB RAM, and Python NetworkX implementation, with performance metrics including execution time, memory usage, scalability, and path accuracy. Comparative analysis against A* search Algorithm, ALT (A* search Landmarks and Triangle inequality), and Arc Flags algorithms demonstrated that Dijkstra consistently achieved faster computation times (up to 40% improvement), lower memory overhead, and higher accuracy in path selection, resulting in significant reductions in delivery and planning time. The findings confirm Dijkstra’s enduring relevance in modern applications such as GPS navigation, logistics management, and network routing. Furthermore, the study highlights opportunities for integrating Dijkstra’s algorithm with real-time traffic data and intelligent systems to enhance adaptive route optimization in dynamic environments
This paper presents a comprehensive comparative study of classical and heuristic shortest path algorithms, with a specific focus on their integration into the classical Transportation Problem (TP). In the conventional TP, the unit transportation cost between a supply node and a demand node is treated as a fixed constant, independent of the underlying network. In real logistics systems, however, this cost arises from the shortest route through a network of intersections and links. To bridge this gap, the present work models the transportation infrastructure as a directed weighted graph and redefines each TP cost coefficient, c_ij’ as the cost of a shortest path between node ‘i’ and node ‘j’. Dijkstra’s algorithm is implemented as the primary engine for computing these network-derived costs and is compared against the Bellman–Ford algorithm and the A* search algorithm under varying network sizes and densities. Simulation experiments on random and grid-based networks with 100–5000 nodes provide a mathematically grounded and empirically validated analysis of time complexity, scalability, and runtime variability. The results show that Dijkstra’s algorithm remains the benchmark for non-negative edge-weight networks, while A* can be faster when an admissible spatial heuristic is available. Bellman–Ford offers flexibility in handling negative weights but becomes computationally prohibitive for large-scale cost-matrix generation. The study establishes a route-aware TP modelling framework and provides practical guidance on algorithm selection for large-scale logistics and transportation planning.
Mrs.Vijayalaxmi, Tanaji S. Pawar· International Research Journ...· 0 citations
The Single Source Shortest Path (SSSP) problem focuses on finding the shortest paths from a source vertex to all other vertices in a graph. This problem is crucial in various domains, including transportation, telecommunications and urban planning. Although Dijkstra's algorithm is effective for solving the SSSP in general cases, in some special cases, such as two-dimensional mesh networks (2DMN), its performance is not satisfactory. To address this limitation, this paper presents an improved approach, i.e., the row-by-row dynamic programming (RRDP) algorithm, which is specifically optimized for 2DMNs and can significantly reduce computation times, although in worst case the complexity of RRDP is higher than Dijkstra's algorithm. We tested the RRDP algorithm against the traditional Dijkstra's algorithm using the same 2DMN instances, and found that RRDP runs much faster than Dijkstra's algorithm on most instances. This innovation offers new insights and practical solutions for improving path planning algorithms in grid network environments.
S. Sun, Yuwei Sang, Zhang-Hua Fu· 2026 6th International Confe...· 0 citations
Shortest path algorithms play an essential role in intelligent transportation systems, emergency response planning, and numerous Smart City services. This study investigates the applicability of three well-established graph-based algorithms, namely Dijkstra, Bellman-Ford, and A*, within an emergency transportation framework inspired by the urban road network of Skopje. A two-stage evaluation methodology was adopted. First, scalability experiments were performed on weighted graphs containing 50 to 500 nodes to examine computational efficiency and algorithm behavior as network size increases. Subsequently, a Smart City transportation model was developed and implemented using Java and JavaFX, enabling the simulation and visualization of several emergency scenarios, including ambulance dispatching, road disruptions, and route unavailability situations. The experimental results indicate that all investigated algorithms successfully identify shortest feasible routes when transportation paths exist, whereas the heuristic guidance employed by A* reduces the number of explored nodes and improves execution times, particularly in larger graph instances. The proposed framework illustrates how algorithmic analysis can be complemented by simulation-based case studies to support intelligent transportation applications and emergency management decision-making. Future research will focus on incorporating real-time traffic information, stochastic travel times, and larger transportation networks to provide more realistic emergency routing environments.
Aleksandra Stojanova Ilievska, N. Stojkovikj, L. Lazarova et al.· International Journal of Adv...· 0 citations
This paper presents a comparative analysis of two variants of a classical algorithm for finding the shortest path in a connected graph. The first variant uses an adjacency matrix (AM) to verify the existence of an edge (arc) between two vertices, while the second variant performs the same verification using an adjacency list (AL). The objective of this study is to examine how graph density affects the performance of the two algorithmic modifications depending on the data structure used. A total of 95 graphs were analyzed, grouped into five sets from 100 to 500 in increments of 100. For each group, 19 graphs were generated with densities ranging from 5% to 95% in increments of 5%. The methodology includes analyzing the number of iterations, assignments, and comparisons executed by the algorithms for all graphs. The initial hypothesis assumed that the total number of operations would always be lower when using an AL instead of an adjacency matrix, regardless of graph density. The results demonstrate that this assumption is incorrect: for densities above 82%, the total number of operations is lower when using an adjacency matrix, whereas the AL is more efficient for densities below 82%, with its efficiency increasing as density decreases. These findings are particularly important for mobile technologies, as they support the design of more efficient pathfinding solutions that optimize performance and energy consumption in mobile applications.
V. Kralev, Radoslava Kraleva, Aleksandra Popova· International Journal of Int...· 0 citations
We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the shortest path from $s$ to $t$. We are particularly interested in instances that can be solved in sublinear time. Recently, Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan, and T\v{e}tek proved that (a version of) the bidirectional Dijkstra's algorithm is instance-optimal on positively weighted multigraphs, both directed and undirected, considering the number of vertices and edges queried by the algorithm. However, multigraphs are not the canonical setting for the shortest-path problem. The problem is typically formulated on simple graphs without loops and parallel edges. They therefore left as an open problem whether bidirectional Dijkstra remains instance-optimal on simple weighted graphs. We answer this question, but for simple graphs, the answer is more complex, depending on the setting. We show that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order. In contrast, under the order-dependent model, where incident edges have a given order, we show that bidirectional Dijkstra is not instance-optimal. For simple directed weighted graphs, we show that bidirectional Dijkstra is not instance-optimal under either the order-oblivious or the order-dependent model, being off by a factor of $\Theta(m/n)$ in both cases. We further show that no algorithm can have instance-optimality ratio $o(m/n)$ under the order-dependent model, or under the order-oblivious model when $m=O(n\sqrt{n})$. On the positive side, the above results imply that bidirectional Dijkstra is instance-optimal up to logarithmic factors on all sparse directed and undirected graphs satisfying $m/n=\log^{O(1)} n$.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
The findings demonstrate that metaheuristic techniques consistently outperform traditional algorithms in complicated, constraint-rich situations and emphasize the need of cost-effective, data-driven metaheuristic optimization in current logistics planning.
K. Khaw, C. Tan· International Journal on Rob...· 0 citations