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

<p>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.</p>

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

CC BY-SA 3.0
2016-08-05T12:02:18.820Z
2016-08-05T12:02:18.820Z
Mister R
<p>$G$ - directed graph,
$n$ - count of nodes</p>

<p>According to Eppstein's Algorithm in <a href="http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf" rel="nofollow">this</a> paper, the <strong>i</strong>th shortest path in a digraph may have $\Omega(ni)$ edges.</p>

<p>Anybody can explain how this estimate is taken?</p>

CC BY-SA 3.0
2016-07-28T00:59:26.657Z
Consider a directed cycle on n vertices.
Igor Shinkar
<cc.complexity-theory><graph-theory><graph-algorithms>
The number of edges in the ith shortest path in a directed graph
Andrei
# The number of edges in the ith shortest path in a directed graph

(Asked by: username_0 on 2016-07-27)

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

According to Eppstein's Algorithm in [this](http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf) paper, the **i**th shortest path in a digraph may have $\Omega(ni)$ edges.

Anybody can explain how this estimate is taken?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Consider a directed cycle on n vertices.  

---

## 1 answers

### Answer by username_2 on 2016-08-05. Score: 0 | Accepted answer

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


---

