The number of edges in the ith shortest path in a directed graph

Question

$G$ - directed graph, $n$ - count of nodes

According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges.

Anybody can explain how this estimate is taken?

Answer 1

As Igor said- Consider a directed cycle with n vertices $C=(v_1,v_2,\ldots,v_n,v_1)$.

The shortest path between $v_1$ and $v_n$ is the path $(v_1,v_2,\ldots, v_n)$ and goes through $n-1$ edges. The second shortest path between $v_1$ and $v_n$ completes a cycle $C$ once, and then uses the path $(v_1,v_2,\ldots, v_n)$. It uses $2n-1$ edges.

The $i^{th}$ shortest path uses $in-1=\theta(in)$ edges