6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

We revisit the shortest paths problem, considering the case where the input is a directed minor-free graph with negative arc lengths (but no negative-length cycles).

In Lecture 14, we saw almost-linear-time algorithms for the case of planar and bounded-genus graphs. Currently, comparable bounds for minor-free graphs are not known. We shall discuss Goldberg's algorithm, a shortest-path algorithm for general graphs with integer lengths, whose running time depends logarithmically on the magnitude of the largest negative arc length. By exploiting separators (Lecture 6), it runs faster on minor-free graphs than on general graphs, but it still requires superlinear time.