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

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari

[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book] [Accessibility]

Lecture 11 Video [previous] [next]

[+] Multiple-source shortest paths.

Based on interdigitating trees from Lecture 2 (they're ubiquitous!) and dynamic trees, we discuss how to efficiently transform a shortest-path tree rooted at r into an SP tree rooted at its neighbor r', and then on to r'', for all the nodes on any face of a planar graph. We shall see that, by doing so, we can compute the shortest-path distance from all the nodes on a single face in time O(n log n) (plus roughly the number of distances output).

Download Video: 360p, 720p

Lecture notes, page 1/6 • [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 Erik.