Shortest Path Algorithms for Smart City Emergency Routing: Scalability and Scenario-Based Analysis

Abstract

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.