SHORTEST PATH OPTIMIZATION IN TRANSPORTATION NETWORKS USING DIJKSTRA’S ALGORITHM: A CASE STUDY OF THE MACEDONIAN ROAD NETWORK

Abstract

Efficient route determination in transportation networks represents an important challenge in modern navigation systems, logistics planning, and traffic management. Models based on graph theory provide an appropriate mathematical framework for representing road infrastructure and analyzing optimal paths between different locations. This paper examines the application of Dijkstra’s algorithm for solving the shortest-path problem in transportation networks modeled as weighted graphs. In the proposed model, cities in the Republic of North Macedonia are represented as vertices, while road connections between them are modeled as edges whose weights correspond to real geographical distances expressed in kilometers. To demonstrate the practical applicability of the proposed approach, a software application implemented in the Java programming language was developed. The system enables users to select a starting and a destination location, after which the algorithm automatically computes the shortest route within the modeled transportation network. The developed model illustrates how graph algorithms can be applied in the analysis and optimization of real transportation systems. The results obtained from the analysis of the modeled road network indicate that the algorithm efficiently identifies optimal routes and supports decision-making in route planning. The study confirms that Dijkstra’s algorithm represents a reliable and computationally efficient method for solving shortest-path problems in road networks. The proposed approach has potential applications in navigation systems, transportation planning, and logistics optimization, highlighting the practical significance of graph algorithms in modern transportation infrastructures..