Department Seminar Series

The challenges of implementing Dijkstras algorithm

9th January 2023, 13:00 add to calender6th Floor Conference Room 605, EEE
Prof. Gerth Stølting Brodal
Department of Computer Science, Aarhus University

Abstract

Any introductory textbook on algorithms considers Dijkstra's algorithm (Dijkstra 1956) for finding the shortest distance from a source node in a graph to all other nodes in the graph. The standard implementation is to use a priority queue, typically the binary heap (Williams 1964) introduced in the same textbook. Surprisingly, many students are challenged by implementing Dijkstra's algorithm, when using the algorithm to find shortest paths in graphs on the scale of Open Street Map graphs. Instead of getting nearly linear running time, some students get quadratic running time when using the Java built-in priority queue, and wonder why the code gets slow when running on graphs with millions of nodes. Many students get slightly wrong distances on a few distance queries, and blame it on numerical issues. The real issue is a subtle misusage of the Java priority queue interface. A common implementation of Dijkstra's algorithm fails to work correctly with the provided built-in binary heap because it misuses Java's priority queue comparator interface. Surprisingly, the same algorithm works correctly with essentially any other priority queue implementing satisfying this priority queue interface. This observation lead us to the introduction of the notion of priority queues supporting decreasing keys (not to be confused with a priority queue supporting a decrease-key operation), allowing for a slightly reduced space usage in Dijkstra's algorithm.

This talk is based on work presented at the 11th International Conference on Fun with Algorithms (FUN 2022).
add to calender (including abstract)

Biography

Gerth Stølting Brodal is a Professor at Aarhus University, Denmark. He received his PhD in computer science from Aarhus University in 1997 for a thesis on “Worst Case Efficient Data Structures”. From 1997 to 1998 he was a PostDoc in the group of Kurt Mehlhorn at the Max-Planck-Institute for Computer Science in Saarbrücken, Germany. Since 1998 he has been at Aarhus University, where he 1998–2005 was affiliated with the Center for Basic Research in Computer Science (BRICS) and 2007–2017 with the Center for Massive Data Algorithmics (MADALGO), both founded by the Danish National Research Foundation.

His main research interests are the design and analysis of algorithms and data structures. He has done work on fundamental data structures, including dictionaries and priority queues, persistent data structures, computational geometry, graph algorithms, string algorithms, I/O-efficient and cache-oblivious algorithms and data structures, algorithm engineering, and computational biology.

Additional Materials