BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260914T182927Z
UID:Seminar-dept-1026@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230109T130000
DTEND:20230109T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Gerth Stølting Brodal: The challenges of implementing Dijkstras algorithm\n\nAny 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.\n\n\n\nThis talk is based on work presented at the 11th International Conference on Fun with Algorithms (FUN 2022).\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1026
LOCATION:6th Floor Conference Room 605, EEE
END:VEVENT
END:VCALENDAR