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?

$\endgroup$
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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