Jul 2026· 2026 6th International Conference on Electrical, Computer and Energy Technologies (ICECET)· pp. 1-8· 0 citations· 28 references
Abstract
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.
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
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.
O. Uchechi, Dennis Mary Chinonye, Oparauwah Nnaemeka Macdonald· International journal of res...· 0 citations
It is shown 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, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
Centroids are used to compute an arbitrary number of simple paths with some important benefits: the expansion of a single centroid delivers an arbitrary number of paths; only a single Dijk-stra search is required to complete the task; the same algorithm can be easily coupled with heuristics that improve search efficiency.
This work considers the problem of finding, for a given degree sequence, the network structure displaying the smallest possible average shortest-path length and proposes a fast algorithm to construct approximate solutions to such a degree-constrained distance-minimization problem.
Under the APSP conjecture, no algorithm solves the narrow core in O ( m √ n polylog( nC )) time for all polynomially bounded integer costs: the decomposition confines the known hardness of 2-SP to a small, explicitly described class of detours.
A. Sedeño-Noda· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
