Improving the Cache-Efficiency of Shortest Path Search

Stefan Edelkamp*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

3 Citations (Scopus)


Flood-filling algorithms as used for coloring images and shadow casting show that improved locality greatly increases the cache performance and, in turn, reduces the running time of an algorithm. In this paper we look at Dijkstra’s method to compute the shortest paths for example to generate pattern databases. As cache-improving contributions, we propose edge-cost factorization and flood-filling the memory layout of the graph. We conduct experiments in commercial game maps and compare the new priority queues with advanced heap implementations as well as and with alternative bucket implementations.

Original languageEnglish
Title of host publicationKI 2017: Advances in Artificial Intelligence - 40th Annual German Conference on AI, Proceedings
PublisherSpringer Verlag
Number of pages15
Volume10505 LNAI
ISBN (Electronic)978-3-319-67190-1
ISBN (Print)9783319671895
Publication statusE-pub ahead of print - 19 Sept 2017
Event40th Annual German Conference on Artificial Intelligence, KI 2017 - Dortmund, Germany
Duration: 25 Sept 201729 Sept 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10505 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference40th Annual German Conference on Artificial Intelligence, KI 2017


Dive into the research topics of 'Improving the Cache-Efficiency of Shortest Path Search'. Together they form a unique fingerprint.

Cite this