2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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)... $\endgroup$ Oct 27, 2017 at 17:42
  • $\begingroup$ 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 :-) $\endgroup$
    – Shuzheng
    Oct 27, 2017 at 17:45
  • $\begingroup$ This may help, but I'm guessing that there is no magic here, that you have to test each starting vertex independently. $\endgroup$
    – rogerl
    Oct 27, 2017 at 18:47
  • $\begingroup$ @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. $\endgroup$
    – Qudit
    Oct 27, 2017 at 19:33
  • $\begingroup$ @Qudit nice solution (+1), but I'm not sure that $|V|^2$ constitutes "efficient"... $\endgroup$
    – rogerl
    Oct 28, 2017 at 13:14

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ What does “n” denote in complexity? Why not just write “|V|”? $\endgroup$
    – Shuzheng
    Oct 28, 2017 at 7:56
  • $\begingroup$ @Shuzheng No particular reason. I wrote $n$ out of habit but it is more consistent to use $|V|$ for both. $\endgroup$
    – Qudit
    Oct 28, 2017 at 8:05
  • $\begingroup$ The all-pairs shortest path algorithm is pretty “hard” to implement, right? It is not a short implementation, or? $\endgroup$
    – Shuzheng
    Oct 28, 2017 at 11:53
  • $\begingroup$ @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. $\endgroup$
    – Qudit
    Oct 28, 2017 at 16:37
  • $\begingroup$ Nice, have you made the above algorithm yourself? Or can I find it in some book? $\endgroup$
    – Shuzheng
    Oct 28, 2017 at 16:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .