Algorithms for Planar Graphs (Fall 2015)

Shay Mozes

Lecture 9 Video [previous] [next]

[+] Shortest Paths in Dense Distance Graphs

The topic of this lecture is an implementation of Dijkstra's algorithm on dense distance graphs, due to Fakcharoenphol and Rao. The running time is nearly linear in the number of vertices of the DDG, rather than in the number of edges as in a naive implementation of Dijkstra's algorithm. At the end of the lecture we start discussing exact distance oracles.

Download Video: 720p

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