Algorithms for Planar Graphs (Fall 2013)

Shay Mozes

Lecture 6 Video [previous] [next]

[+] Shortest Paths with Negative Lengths

We start with a recap of the MSSP algorithm and discuss how the data structure can be used to report shortest paths and distances. The bulk of this lecture is devoted to a nearly-linear time algorithm for shortest paths in the presence of negative lengths. The heart of the algorithm is a procedure to implement the Bellman-Ford algorithm on the dense distance graph - the complete graph on vertices of a cycle separator, where the length of an edge in the DDG corresponds to the length of a shortest path between its endpoints in the underlying planar graph. We show that implementing an iteration of Bellman-Ford can be cast into the problem of finding all column minima in the weighted incidence matrix of the DDG. We then introduce the Monge property, and show that we can find all column minima of a Monge matrix in time that is nearly linear in the number of rows. Finally we show that the weighted incidence matrix of the DDG can be decomposed into a small number of Monge matrices.

Download Video: 360p, 720p

Lecture notes, page 1/17 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email me.