  We study the problem of computing shortest paths in so-called dense distance
graphs. Every planar graph $G$ on $n$ vertices can be partitioned into a set of
$O(n/r)$ edge-disjoint regions (called an $r$-division) with $O(r)$ vertices
each, such that each region has $O(\sqrt{r})$ vertices (called boundary
vertices) in common with other regions. A dense distance graph of a region is a
complete graph containing all-pairs distances between its boundary nodes. A
dense distance graph of an $r$-division is the union of the $O(n/r)$ dense
distance graphs of the individual pieces. Since the introduction of dense
distance graphs by Fakcharoenphol and Rao, computing single-source shortest
paths in dense distance graphs has found numerous applications in fundamental
planar graph algorithms.
  Fakcharoenphol and Rao proposed an algorithm (later called FR-Dijkstra) for
computing single-source shortest paths in a dense distance graph in
$O\left(\frac{n}{\sqrt{r}}\log{n}\log{r}\right)$ time. We show an
$O\left(\frac{n}{\sqrt{r}}\left(\frac{\log^2{r}}{\log^2\log{r}}+\log{n}\log^{\epsilon}{r}\right)\right)$
time algorithm for this problem, which is the first improvement to date over
FR-Dijkstra for the important case when $r$ is polynomial in $n$. In this case,
our algorithm is faster by a factor of $O(\log^2{\log{n}})$ and implies
improved upper bounds for such planar graph problems as multiple-source
multiple-sink maximum flow, single-source all-sinks maximum flow, and (dynamic)
exact distance oracles.
