[+] Singlesource shortest paths: Nonnegative lengths in planar graphs. 
We see how to improve upon Dijkstra's algorithm for the SSSP problem in planar graphs with nonnegative edge lengths. As an important technique, we revisit the concept
of an rdivision.
In the previous lecture, we saw how to recursively separate a planar graph into small pieces with small total boundary. In this lecture, we see how to obtain a socalled rdivision, where each individual piece is guaranteed to have small boundary (as opposed to small total boundary as in the previous lecture). We also discuss how to quickly compute such an rdivision. Using an algorithm for fast rdivision, we obtain a simple SSSP algorithm for planar graphs that's faster than Dijkstra's algorithm. We then discuss an even faster algorithm for SSSP in planar graphs. Despite the algorithm being quite simple, somewhat surprisingly, a rather involved analysis proves that its running time is linear, which is asymptotically optimal! We analyze a simplified version running in time O(n log logn). The algorithm works a little bit like Dijkstra's algorithm with “limited attention span”: The simple version starts by decomposing the graph into pieces of size O(log^{4} n). Then, it repeatedly works on the piece with the current minimum for log n steps until the shortestpath distance to all nodes has been found. We (partially) analyze the running time of the simplified algorithm. 
Lecture notes, page 1/10 •
[previous page] •
[next page] •
[PDF]
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 Erik.