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$?
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.