Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as minimal total weight as possible. Is there a name for this? It's bounded below by the minimum spanning tree of $G$, but bounded above by the travelling salesman tour of $G$, so I'm curious if it's been studied previously in the literature.
$\begingroup$ $\endgroup$
1 
- $\begingroup$ This is similar (but not quite the same) as the shortest-path tree constructed by Dijkstra's algorithm. $\endgroup$Tony Huynh– Tony Huynh2016-01-21 22:25:27 +00:00Commented Jan 21, 2016 at 22:25
Add a comment |