<p>I am assuming you are given a weighted directed acyclic graph with source $s$ and destination $t$ and you want to find the shortest path from $s$ to $t$ with length exactly $n$ , this can be done easily with dynamic programming. Let $F(v,k)$ denote the shortest path from $v$ to $t$ with length exactly $k$ , we have<br> $F(t , k) = \begin{cases}
  0 \ \ \ \ \text{ if }k = 0\\    
  +\infty \ \text{if } k &gt; 0    
\end{cases}$.<br> and<br>
$F(v , k) = \begin{cases}
  \infty \text{ if }k = 0\\    
  \min_{u \in N^{+}(v)} F(u , k-1)+W(v,u)   
\end{cases}$ <br>
Solution is $F(s,n)$.</p>

CC BY-SA 4.0
2018-07-26T19:25:41.140Z
Thanks! But is this method any more efficient than the one I posted in my original question? It seems like this will try every possible path from `s` to `t` in order to generate the answer.
Reubend
CC BY-SA 4.0
2018-07-26T21:04:08.447Z
@Reubend: it doesn't try every possible path. If there are two paths (b,c,t) and (b,d,t) from b to t, and (b,c,t) is longer, then it never worries about (a,b,c,t).
Peter Shor 
CC BY-SA 4.0
2018-07-26T12:19:56.827Z
2018-07-26T12:19:56.827Z
Rajat De
<p>Given a weighted directed acyclic graph, how can I find the cheapest path from an <code>Origin Vertex</code> to a <code>Destination Vertex</code> which goes through exactly <code>n</code> vertices? </p>

<p>Is there an efficient algorithm which accomplishes this? I know that I could use BFS to find all the possible paths between them, then filter that to get only the ones which are <code>n</code> long, and then sort them by cost. However, I would like to know if there's an algorithm which does not need to consider all possible paths to generate the result.</p>

CC BY-SA 4.0
2018-07-25T20:42:11.037Z
What do you mean by efficient?
daniello
CC BY-SA 4.0
2018-07-25T20:44:17.960Z
I'll edit my question to clarify. I mean an algorithm which does not have to consider all possible paths, only n-paths, in order to generate the result.
Reubend
CC BY-SA 4.0
2018-07-26T12:52:23.797Z
The problem seems to be $\mathsf{NP}$-complete, since it reduces to Hamiltonian path in a DAG (just take $n=|V|$). May be this link can be useful: https://stackoverflow.com/questions/16124844/algorithm-for-finding-a-hamilton-path-in-a-dag
Lamine
CC BY-SA 4.0
2018-07-26T20:46:57.183Z
@PeterShor Forgive me if I'm being stupid here, but wouldn't it be impossible to visit the same node twice in a DAG? I think there would be a cycle if you could ever go back to somewhere you already visited, so it wouldn't be acyclical.
Reubend
CC BY-SA 4.0
2018-07-26T20:58:45.773Z
Of course it would. I didn't notice the DAG restriction.
Peter Shor 
<graph-theory><graph-algorithms><directed-acyclic-graph><shortest-path>
Finding Cheapest n-Path
Reubend
# Finding Cheapest n-Path

(Asked by: username_0 on 2018-07-25)

Given a weighted directed acyclic graph, how can I find the cheapest path from an `Origin Vertex` to a `Destination Vertex` which goes through exactly `n` vertices?

Is there an efficient algorithm which accomplishes this? I know that I could use BFS to find all the possible paths between them, then filter that to get only the ones which are `n` long, and then sort them by cost. However, I would like to know if there's an algorithm which does not need to consider all possible paths to generate the result.

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph, shortest-path

> **Comments:**
> **username_1**: What do you mean by efficient?  
> **username_0**: I'll edit my question to clarify. I mean an algorithm which does not have to consider all possible paths, only n-paths, in order to generate the result.  
> **username_2**: The problem seems to be $\mathsf{NP}$-complete, since it reduces to Hamiltonian path in a DAG (just take $n=|V|$). May be this link can be useful: https://stackoverflow.com/questions/16124844/algorithm-for-finding-a-hamilton-path-in-a-dag  
> **username_0**: @PeterShor Forgive me if I'm being stupid here, but wouldn't it be impossible to visit the same node twice in a DAG? I think there would be a cycle if you could ever go back to somewhere you already visited, so it wouldn't be acyclical.  
> **username_3**: Of course it would. I didn't notice the DAG restriction.  

---

## 1 answers

### Answer by username_4 on 2018-07-26. Score: 1

I am assuming you are given a weighted directed acyclic graph with source $s$ and destination $t$ and you want to find the shortest path from $s$ to $t$ with length exactly $n$ , this can be done easily with dynamic programming. Let $F(v,k)$ denote the shortest path from $v$ to $t$ with length exactly $k$ , we have  
 $F(t , k) = \begin{cases}
0 \ \ \ \ \text{ if }k = 0\\
+\infty \ \text{if } k > 0
\end{cases}$.  
 and  
$F(v , k) = \begin{cases}
\infty \text{ if }k = 0\\
\min\_{u \in N^{+}(v)} F(u , k-1)+W(v,u)
\end{cases}$   
Solution is $F(s,n)$.

> **Comments:**
> **username_0**: Thanks! But is this method any more efficient than the one I posted in my original question? It seems like this will try every possible path from `s` to `t` in order to generate the answer.  
> **username_3**: @username_0: it doesn't try every possible path. If there are two paths (b,c,t) and (b,d,t) from b to t, and (b,c,t) is longer, then it never worries about (a,b,c,t).  

---

