-2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ What do you mean by efficient? $\endgroup$
    – daniello
    Jul 25, 2018 at 20:42
  • $\begingroup$ 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. $\endgroup$
    – Reubend
    Jul 25, 2018 at 20:44
  • 1
    $\begingroup$ 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: stackoverflow.com/questions/16124844/… $\endgroup$
    – Lamine
    Jul 26, 2018 at 12:52
  • $\begingroup$ @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. $\endgroup$
    – Reubend
    Jul 26, 2018 at 20:46
  • $\begingroup$ Of course it would. I didn't notice the DAG restriction. $\endgroup$
    – Peter Shor
    Jul 26, 2018 at 20:58

1 Answer 1

Reset to default
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Reubend
    Jul 26, 2018 at 19:25
  • 1
    $\begingroup$ @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). $\endgroup$
    – Peter Shor
    Jul 26, 2018 at 21:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.