I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s to vertex t using at least k edges but less than 20. No vertex may be repeated in a path.

I am aware of this problem: Dijkstra's algorithm to compute shortest paths using k edges?

That problem wants to find the shortest paths using at most k edges.

My current idea is to create the product graph via V' = V x {0, 1, 2, ..., 20} and then ignore any shortest paths from (s, 0) to (t, n) where n < k. However, because the product construction essentially duplicates nodes, I am not aware of a way to ignore duplicate vertices in the path-finding algorithm.

P.S. If k were very large, say, k = |V|, wouldn't this be the Hamiltonian path problem and therefore NP-complete?

  • 3
    $\begingroup$ For the PS: yes, it does include Hamiltonian Path Problem as a subproblem. $\endgroup$ Apr 9, 2019 at 17:10
  • $\begingroup$ @John Dvorak the linked problem gave a worst case complexity of 𝑂(𝑘⋅(|𝑉|+|𝐸|)lg|𝐸) and it includes the Hamiltonian Path Problem if k = |V| and there are no paths for k less than this. Am I mistaken? $\endgroup$ Apr 9, 2019 at 17:46
  • 1
    $\begingroup$ @csquestions, if you are not allowed cycles, then this is NP-complete. See this question, specifically the first and last bullet point. Also see last paragraph of this answer to that question. $\endgroup$
    – ryan
    Apr 9, 2019 at 17:52
  • 1
    $\begingroup$ if you allow cycles, then you can either replicate the graph $k$ times, or apply some dynamic programming approach. Since you don't, it's NP-complete $\endgroup$
    – lox
    Apr 9, 2019 at 17:57

1 Answer 1


Unfortunately, your problem is NP Complete, since you require that no vertex will be visited twice.

Consider we had a polynomial time solution for some $k$. For clarification; given an undirected graph $G=(V,E)$ and two vertices $s,t$, we can find a shortest path from $s$ to $t$ of length $\geq k$ in polynomial time. Then, by extension we can solve in polynomial time for $k=n-1$ and thus find a path that visits eeach vertex in $V$ exactly once. In other words, we can "solve" Hamiltonian Path.

If you know in advance that $k \leq 20$ then you can exhaustive search all paths of length at most 20, and therefore solve for small $k$.

An exhaustive search, at worst, is to search every vertex order starting from $s$ that ends in $t$ (corresponding to existing edges), so in total you will search: $$(n-1)(n-2)(n-3)...(n-20) = O(n^{20})$$


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.