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?

  • $\begingroup$ In addition to what @D.W. said, I would suggest Lin-Kernighan heuristic $\endgroup$ Commented Sep 1, 2018 at 8:08
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Sep 2, 2018 at 7:58
  • $\begingroup$ @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. $\endgroup$ Commented Sep 2, 2018 at 8:00
  • 1
    $\begingroup$ So a path is going from grid point to grid point, and the same grid point must not be used twice? $\endgroup$
    – gnasher729
    Commented Jan 1, 2019 at 10:37
  • $\begingroup$ gnasher729's question is important. Knowing the points lie on a grid and the edges are the grid neighborhood relation allows more efficient solutions. $\endgroup$ Commented Jan 31, 2019 at 16:48

1 Answer 1


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.

  • $\begingroup$ You reduce this problem to minimum-cost integer multi-commodity flow problem, which is not sufficient to show this problem is NP-complete. $\endgroup$
    – xskxzr
    Commented Jan 1, 2019 at 4:45
  • $\begingroup$ @xskxzr Right. I removed that claim. $\endgroup$
    – orlp
    Commented Jan 1, 2019 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.