Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 3 Video [previous] [next]

[+] Multiple Source Shortest Paths

We discuss an O(nlogn) time algorithm that, given a directed planar graph with dart lengths and a distinguished face f, computes a representation of all the shortest path trees rooted at vertices of f. The algorithm is based on interdigitating trees and uses dynamic trees to represent the trees efficiently.

Download Video: 720p

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