  Given a distributed network represented by a weighted undirected graph
$G=(V,E)$ on $n$ vertices, and a parameter $k$, we devise a distributed
algorithm that computes a routing scheme in $(n^{1/2+1/k}+D)\cdot n^{o(1)}$
rounds, where $D$ is the hop-diameter of the network. The running time matches
the lower bound of $\tilde{\Omega}(n^{1/2}+D)$ rounds (which holds for any
scheme with polynomial stretch), up to lower order terms. The routing tables
are of size $\tilde{O}(n^{1/k})$, the labels are of size $O(k\log^2n)$, and
every packet is routed on a path suffering stretch at most $4k-5+o(1)$. Our
construction nearly matches the state-of-the-art for routing schemes built in a
centralized sequential manner. The previous best algorithms for building
routing tables in a distributed small messages model were by \cite[STOC
2013]{LP13} and \cite[PODC 2015]{LP15}. The former has similar properties but
suffers from substantially larger routing tables of size $O(n^{1/2+1/k})$,
while the latter has sub-optimal running time of
$\tilde{O}(\min\{(nD)^{1/2}\cdot n^{1/k},n^{2/3+2/(3k)}+D\})$.
