# 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?

• In addition to what @D.W. said, I would suggest Lin-Kernighan heuristic – Sandro Lovnički Sep 1 '18 at 8:08
• The solution you suggest isn't optimal. A shorter solution is to make the A-B path go north of D, like this. This gives cost 22, whereas your solution has cost 24. – David Richerby Sep 2 '18 at 7:58
• @D.W. I'm not sure TSP algorithms will be much use: in this situation, the order of the cities is fixed and the difficulty is that we might need to pick a suboptimal route between one pair of cities to save space later on. – David Richerby Sep 2 '18 at 8:00
• So a path is going from grid point to grid point, and the same grid point must not be used twice? – gnasher729 Jan 1 at 10:37
• gnasher729's question is important. Knowing the points lie on a grid and the edges are the grid neighborhood relation allows more efficient solutions. – reinierpost Jan 31 at 16:48

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.