  Let G be a directed graph with n vertices and non-negative weights in its
directed edges, embedded on a surface of genus g, and let f be an arbitrary
face of G. We describe a randomized algorithm to preprocess the graph in O(gn
log n) time with high probability, so that the shortest-path distance from any
vertex on the boundary of f to any other vertex in G can be retrieved in O(log
n) time. Our result directly generalizes the O(n log n)-time algorithm of Klein
[SODA 2005] for multiple-source shortest paths in planar graphs. Intuitively,
our preprocessing algorithm maintains a shortest-path tree as its source point
moves continuously around the boundary of f. As an application of our
algorithm, we describe algorithms to compute a shortest non-contractible or
non-separating cycle in embedded, undirected graphs in O(g^2 n log n) time with
high probability. Our high-probability time bounds hold in the worst-case for
generic edge weights, or with an additional O(log n) factor for arbitrary edge
weights.
