We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an $s$-$t$-graph $D(V,A)$ and for each arc a nominal length $c(a)$ and a maximal increase $d(a)$ of its length. We consider all scenarios in which for the increased lengths $c(a) + \bar{d}(a)$ we have $\sum_{a\in A}\frac{\bar{d}(a)}{d (a)} \leq \Gamma$. Each path is measured by the length in its worst-case scenario. A classic result minimizes this path length by solving $(|A| + 1)$-many shortest path problems. Easily, $(|A| + 1)$ can be replaced by $|\Theta|$, where $\Theta$ is the set of all different values $d(a)$ and $0$. Still, the approach remains impractical for large graphs. Using the monotonicity of a part of the objective we devise a Divide and Conquer method to evaluate significantly fewer values of $\Theta$. This methods generalizes to binary linear robust problems. Specifically for shortest paths we derive a lower bound to speed-up the Divide and Conquer of $\Theta$. The bound is based on carefully using previous shortest path computations. We combine the approach with non-preprocessing based acceleration techniques for Dijkstra adapted to the robust case. In a computational study we document the value of different accelerations tried in the algorithm engineering process. We also give an approximation scheme for the robust shortest path problem which computes a $(1 + \epsilon)$-approximate solution requiring $\O(\log(1 + \epsilon)^{-1})$ computations of the nominal problem.