Finding the Shortest Path

Dr. Pettie graduated from U. Texas at Austin in 2003; he is presently a postdoc at Max Planck Institut fur Informatik in Germany.
What's the shortest route from point A to point B? This is a fundamental algorithmic question with deep connections to other optimization problems and numerous practical applications. The most well known applications are services like Google Maps, OnStar, and MapQuest, which will quickly answer shortest path queries on the U.S. road network. Although shortest path algorithms are relatively fast in practice, the inherent time complexity of computing shortest paths is unresolved. In fact, on general graphs this problem has seen surprisingly little progress since the invention of the "textbook" algorithms of Dijkstra, Bellman-Ford, and Floyd-Warshall in the late 1950s.

In the first part of this talk I'll present an asymptotically faster all-pairs shortest path algorithm for general graphs. This is the first such algorithm to improve the running time of Dijkstra's algorithm.

In many scenarios finding shortest paths is only the beginning. The more challenging problem is to encode shortest path information in a succinct and usable way. (For instance, in the form of routing tables distributed across the nodes of a network.) In the second part of the talk I'll discuss my work on low-distortion spanners, which are objects that efficiently encode approximately shortest paths.