[+] Multiple Source Shortest Paths 
We develop an O(n log n)time algorithm that, given a shortest path tree rooted at some vertex r of a face f in a directed planar graph, computes a representation of all shortest path trees rooted at all vertices of f. This representation can be used to report distances between any vertex of f and any other vertex in the graph in O(log n) time. The algorithm is based on interdigitating trees and uses dynamic trees to represent the trees efficiently. 
Lecture notes, page 1/13 •
[previous page] •
[next page] •
[PDF]
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.