The heuristic search community traditionally uses A* as the baseline algorithm for their research methods. Research papers in the road networks community, however, often build upon Dijkstra's algorithm and use Bidirectional Dijkstra's algorithm as their baseline. This thesis investigates the performance of A* and Bidirectional Dijkstra in road networks to see how they compare and to see if there is a principled explanation for the different approaches. Our analysis reveals why Bidirectional Dijkstra can perform well in this domain, but also shows a simple mistake that can be made when building test problems that hurts the performance of A*.
","abstract_html":"<p>The heuristic search community traditionally uses A* as the baseline algorithm for their research methods. Research papers in the road networks community, however, often build upon Dijkstra's algorithm and use Bidirectional Dijkstra's algorithm as their baseline. This thesis investigates the performance of A* and Bidirectional Dijkstra in road networks to see how they compare and to see if there is a principled explanation for the different approaches. Our analysis reveals why Bidirectional Dijkstra can perform well in this domain, but also shows a simple mistake that can be made when building test problems that hurts the performance of A*.</p>","abstract_has_math":false,"creators":["Sawlani, Sneha"],"institution":null,"degree_name":"M.S.","degree_level":"Masters Thesis","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Nathan Sturtevant, Ph.D.","Chris Gauthier-Dickey","Mei Yin"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-01-01T08:00:00Z","date_published":"2017-01-01T08:00:00Z","updated_at":"2026-07-24T02:02:53Z","subjects":["A*","Bidirectional dijkstra","Dijkstra's algorithm","Road networks","Search algorithms","Computer Engineering"],"languages":["en"],"rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/1303","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nathan Sturtevant, Ph.D.","Chris Gauthier-Dickey","Mei Yin"]},{"key":"dc:creator","label":"Author","values":["Sawlani, Sneha"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2017-07-25T07:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["A*","Bidirectional dijkstra","Dijkstra's algorithm","Road networks","Search algorithms","Computer Engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author. User is responsible for all copyright compliance.
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/1303"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The heuristic search community traditionally uses A* as the baseline algorithm for their research methods. Research papers in the road networks community, however, often build upon Dijkstra's algorithm and use Bidirectional Dijkstra's algorithm as their baseline. This thesis investigates the performance of A* and Bidirectional Dijkstra in road networks to see how they compare and to see if there is a principled explanation for the different approaches. Our analysis reveals why Bidirectional Dijkstra can perform well in this domain, but also shows a simple mistake that can be made when building test problems that hurts the performance of A*.
"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Explaining the Performance of Bidirectional Dijkstra and A* on Road Networks"]}]}],"canonical_facts":{"dc:contributor":["Nathan Sturtevant, Ph.D.","Chris Gauthier-Dickey","Mei Yin"],"dc:creator":["Sawlani, Sneha"],"dc:date.available":["2017-07-25T07:00:00Z"],"dc:description.abstract":["The heuristic search community traditionally uses A* as the baseline algorithm for their research methods. Research papers in the road networks community, however, often build upon Dijkstra's algorithm and use Bidirectional Dijkstra's algorithm as their baseline. This thesis investigates the performance of A* and Bidirectional Dijkstra in road networks to see how they compare and to see if there is a principled explanation for the different approaches. Our analysis reveals why Bidirectional Dijkstra can perform well in this domain, but also shows a simple mistake that can be made when building test problems that hurts the performance of A*.
"],"dc:format":["application/pdf"],"dc:identifier":["https://digitalcommons.du.edu/etd/1303"],"dc:language":["en"],"dc:rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"dc:subject":["A*","Bidirectional dijkstra","Dijkstra's algorithm","Road networks","Search algorithms","Computer Engineering"],"dc:title":["Explaining the Performance of Bidirectional Dijkstra and A* on Road Networks"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["M.S."]},"updated_at":"2026-07-24T02:02:53Z"}