$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?
$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?
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