  Due to the computational complexity of finding almost shortest simple paths,
we propose that identifying a larger collection of (nonbacktracking) paths is
more efficient than finding almost shortest simple paths on positively weighted
real-world networks. First, we present an easy to implement $O(m\log m+kL)$
solution for finding all (nonbacktracking) paths with bounded length $D$
between two arbitrary nodes on a positively weighted graph, where $L$ is an
upperbound for the number of nodes in any of the $k$ outputted paths.
Subsequently, we illustrate that for undirected Chung-Lu random graphs, the
ratio between the number of nonbacktracking and simple paths asymptotically
approaches $1$ with high probability for a wide range of parameters. We then
consider an application to the almost shortest paths algorithm to measure path
diversity for internet routing in a snapshot of the Autonomous System graph
subject to an edge deletion process.
