Performance Optimization of Dijkstra and A* Search Algorithms Using Cache ? Aware Graph Structures

Shortest?path algorithms such as Dijkstra and A* are fundamental to route planning, navigation, and intelligent transportation systems. Despite strong theoretical performance, their execution time on large, sparse real?world road networks is dominated by memory latency rather than arithmetic cost. This study introduces cache?aware data?structure design using the Compressed Sparse Row (CSR) format and sequential vertex?blocking to improve memory locality. Experimental results show 2x-4x speedup and significant reductions in L3 cache misses across graph sizes ranging from 5,000 to 100,000 vertices. The findings demonstrate that memory?centric optimization significantly enhances performance in transportation?scale shortest?path search.