Find shortest path that visits all nodes in a given set of nodes Suppose I have a graph $G$ and a set of target nodes $S = \{A_1, ..., A_n\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice.

For example, consider the following:



I have attempted to solve this by first performing a breadth-first search to find the shortest path from A to B, then from B to C, and so on, taking care to exclude any paths already found at each iteration. 

This greedy solution works for most inputs, but in some case it will fail to find a solution, as the shortest path between two target nodes may end up blocking the complete path.

Aside from a brute-force approach, is it possible to find the shortest path that visits all of the target nodes, and is guaranteed to find such a path if one exists? Any suggestions on how to proceed?
I answered a more general problem a couple days ago. You simply want the destination pairs to be (a, b), (b, c), (c,d ),etc.

The gist is to translate the problem into a minimum-cost integer multi-commodity flow problem with a maximum capacity of $1$ per node, and one commodity between each pair of destinations.