# Practical algorithm for finding a path of length $k$ of minimum total weight in graph?

Practical algorithm for finding a path of length $k$ of minimum total weight in graph?

I want to find a path $v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_k$ such that all $v_i$'s are distinct and the sum of the distances on the edges is minimized.

My question is twofold.

Does the above problem have a formal name like TSP or Hamiltonian path problem?

What are the efficient algorithms for solving this problem? I look for algorithms that is "easily" implemented modern programming languages.

Indeed, an algorithm is depth-first search from each vertex, stopping when encountered a path of length $k$?

• Just to make sure that I understand - are you asking for the "least efficient" path of length $k$? The path of length $k$ between two points that are the smallest distance apart? In the cycle $C_6$, if we consider $k=5$, then any two adjacent points are distance 1 apart, but have a path of length $5$ between them (going the "long way" around the cycle)... Oct 27, 2017 at 17:42
• I want to find a path $v_1 \rightarrow v_2 \rightarrow v_3$ such that all $v_i$'s are distinct and the sum of the distances on the edges is minimized :-) Oct 27, 2017 at 17:45
• This may help, but I'm guessing that there is no magic here, that you have to test each starting vertex independently. Oct 27, 2017 at 18:47
• @rogerl The trouble is that the dynamic programming algorithm in your link doesn't require all vertices in a path to be distinct as the OP requested and it's unclear if it can be modified to enforce that requirement. The other algorithm would work but it is very slow. Oct 27, 2017 at 19:33
• @Qudit nice solution (+1), but I'm not sure that $|V|^2$ constitutes "efficient"... Oct 28, 2017 at 13:14

This problem does not have a standard name as far as I know. However, it is NP-hard so there is no general algorithm. Let us define the length of a path to be the number of edges that it contains and the cost of a path to be the sum of the weights of those edges.

To see that the problem is NP-hard observe that a graph $G$ on $n$ vertices contains a Hamiltonian path if and only if it contains a path of length $n - 1$ in which all vertices are distinct. If any such paths exist, then one of them has minimal cost. Thus, the Hamiltonian path problem reduces to your problem for length $k = n - 1$.

Edit: This answer previously gave an algorithm that was completely incorrect. See the comments and revision history.

• What does “n” denote in complexity? Why not just write “|V|”? Oct 28, 2017 at 7:56
• @Shuzheng No particular reason. I wrote $n$ out of habit but it is more consistent to use $|V|$ for both. Oct 28, 2017 at 8:05
• The all-pairs shortest path algorithm is pretty “hard” to implement, right? It is not a short implementation, or? Oct 28, 2017 at 11:53
• @Shuzheng Floyd-Warshall is 11 lines on Wikipedia. Implement that one if you don't mind something a little slower that's easy to implement. Oct 28, 2017 at 16:37
• Nice, have you made the above algorithm yourself? Or can I find it in some book? Oct 28, 2017 at 16:45