On the Comparative Analysis of Shortest Path Algorithms within the Framework of Mathematical Transportation Problems

Abstract

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.