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 HuynhCommented Jan 21, 2016 at 22:25
Add a comment
|