# Djikstra's algorithm to compute shortest paths using at least k edges

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?

• For the PS: yes, it does include Hamiltonian Path Problem as a subproblem. Apr 9, 2019 at 17:10
• @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? Apr 9, 2019 at 17:46
• @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.
– ryan
Apr 9, 2019 at 17:52
• 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
– lox
Apr 9, 2019 at 17:57

## 1 Answer

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