1
$\begingroup$

I am trying to find an efficient algorithm for the following problem:

Input:

  • weighted directed graph G=(V, E) in which all edges are weigthed either 1 or 2
  • s,t ∈ V
  • n ∈ N

Output

  • shortest path from s to t that contains exactly n edges of weight 2

I have been experimenting with different modifications of Bellman-Ford, Dijkstra and even max-flow with no luck.

Is there an efficient algorithm for solving this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

When all edges have weight 2 and $n = |V|$ the problem is equivalent to longest path which is NP-complete. So unless P = NP, there is no efficient algorithm for solving the problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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