[Solved]: Shortest directed path connecting given subset of vertices

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

1. Does such problem have a name?
2. 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