Multiple-Source Shortest Paths in Embedded Graphs
Multiple-Source Shortest Paths in Embedded Graphs
Let $G$ be a directed graph with $n$ vertices and nonnegative 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 …