Abstract
The problem of finding distances and shortest paths on a given graph is one of the most classic problems in algorithmic graph theory. It has been studied for a long time and there are many elegant algorithms developed for various versions of this problem. We discuss the all pairs almost shortest paths problem and the all pairs small stretch paths problem --- both are variations of the all pairs shortest paths (APSP) problem --- with the help of quantum single source shortest paths (SSSP) algorithm on an undirected and connective graph. For the all pairs almost shortest paths problem, the fastest classical algorithm up to the present runs in $\tilde{O}(\min(n^{3/2}m^{1/2}, n^{7/3}))$ time and that for the all pairs small stretch paths problem runs in $\tilde{O}(n^{3/2}m^{1/2})$ time. In this article we present two quantum algorithms $\mathbf{Qapasp_{2}}$ and $\mathbf{Qstretch_2}$ for the all pairs almost shortest paths problem and the all pairs small stretch paths problem, respectively. As shown in Theorems \ref{THM:Qapasp2} and \ref{THM:Qstretch2}, both algorithms run in time $\tilde{O}\left(n^{11/6}m^{1/6}\right)$ and are faster than other known algorithms.