Problem Detail: Given
- weighted directed graph $G = (V,E,w)$, where $w : E to mathbb R^+$
- source vertex $v in V$
- vertex subset $U subset V$
how to find a shortest directed path from $v$ containing all vertices from $U$? Note that such path may contain vertices that are not in $U$.
- Does such problem have a name?
- How to find a solution?
Asked By : Jakub Stejskal
Answered By : Yuval Filmus
This problem is NP-complete, by reduction from Hamiltonian path. Given an instance $G=(V,E)$ of Hamiltonian path, add a new vertex $s$ connected to all original vertices; this edges are directed from $s$, and all the original graph edges are bidirectional. Give all edges unit weight. There is a path from $s$ visiting all of $V$ of weight $|V|$ if and only if $G$ has a Hamiltonian path.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23784
