Downloads: 0
Research Paper | Computer Science and Information Technology | Volume 15 Issue 1, January 2026 | Pages: 1437 - 1438 | United States
Performance Optimization of Dijkstra and A* Search Algorithms Using Cache ? Aware Graph Structures
Abstract: 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.
Keywords: shortest path algorithms, cache aware optimization, memory locality, compressed sparse row, road network graphs
How to Cite?: Prakasharao Raghavapudi, Rashmi Gupta, "Performance Optimization of Dijkstra and A* Search Algorithms Using Cache ? Aware Graph Structures", Volume 15 Issue 1, January 2026, International Journal of Science and Research (IJSR), Pages: 1437-1438, https://www.ijsr.net/getabstract.php?paperid=SR26123032635, DOI: https://dx.dx.doi.org/10.21275/SR26123032635