Finding the Shortest Path that connects k nodes in a graph I was wondering if there are algorithms for finding the shortest path that contains some selected $k$ nodes in a weighted graph. More specifically, the path that we are looking for needs to pass through all the $k$ nodes, but can contain other nodes from the graph and can visit those $k$  nodes in any order. In addition, any node can be traversed more than once. Also, the path has to start and end with two distinct nodes from the given set of $k$ nodes. For example, if $k=2$, we have two nodes, $u_1$ and $u_2$, and are looking for the shortest path from $u_1$ to $u_2$. We can use UCS or $A^*$ to solve this. If $k=3$, there will be three nodes: $u_1$, $u_2$, and $u_3$. The path can start in $u_1$, pass through $u_2$, and finish in $u_3$, or start in $u_2$, pass through $u_1$, and end in $u_3$, etc. $k$ can take any value from $2$ to $n$, $n$ being the total number of nodes in the graph.

To me, this somewhat looks like a problem of finding the minimal tree whose leaves are those $k$ nodes. A path passing through the leaves could then be obtained by traversing the tree in an appropriate order.
The state of a traversal at any point will be (a) the node you're currently at, and (b) the subset of the $k$ selected nodes you've already passed through.  Thus, you can solve this problem by constructing a new graph $G'$ that is $2^k$ times as large as the original graph $G$, and then finding the shortest path in $G'$.

In particular, each vertex of $G'$ has the form $(v,S)$ where $v \in V$ and $S$ is a subset of the $k$ selected nodes; for each edge $v \to w$ in the original graph, $G$' has the edge $(v,S) \to (w,S)$ (if $w$ is not one of the selected $k$) or $(v,S) \to (w,S\cup \{w\})$ (if $w$ is one of the selected $k$).

Unfortunately the running time of this algorithm is exponential in $k$.  I don't expect there to be a polynomial-time solution; David Richerby explains why not.