How to find the shortest path between several nodes in a particular order without ever using any edge twice? Given are a number of ordered nodes in a bidirectional graph with known only positive cost for each edge.
I need to find the shortest path through the given nodes in the particular order that are given while never using any edge twice.
So in contrast to Travelling Salesman problems, I know the order of traversal.
However, the last requirement is key here. Due to not being able to use any edge twice, the locally optimal path between node 1 and 2 could create a suboptimal path between 2 and 3 and so on or even make a complete path impossible.
Right now, I am using A-Star in succession to build the total path, but it is clear that this is not optimal.
So, is there a way to find the global optimum over all given nodes (if it exists at all) by looking at all of them at the same time to find the optimal path?
 A: Even finding out whether there is a solution at all is NP-complete. I will show this by reducing from 3SAT.
Given a 3SAT instance, create a copy of the following 18-node network for each 3-literal clause:

The edges $Y_1\leftrightarrow Z_1$, $Y_2\leftrightarrow Z_2$, and $Y_3\leftrightarrow Z_3$ represent the literal; the connections to the $Y_i$ and $Z_i$ nodes will be made later.
The nodes $A, B, C, D, E, F$ must be visited in that order. The edge going to the right from $F$ connects to the $A$ of the next clause.
The part of the path that visits $ABCDEF$ must use at least one of the $Y_i\leftrightarrow Z_i$ edges. Because $C$ must be visited, at least two of $X_1 X_2 X_3$ must be visited by this part of the path; this prevents any part of the path outside $ABCDEF$ from entering the $BCX_1X_2X_3$ network. (The rules imply that a node of degree $\le 3$ can be used at most once). Similarly on the other side of the fragment, no part of the path outside $ABCDEF$ can enter the $W_1W_2W_3DE$ network.
In addition to these clause networks, for each variable $x_n$ in the 3SAT problem have nodes $P_n, Q_n$ that must be visited in this order. Add a path from $P_n$ to $Q_n$ that passes through all the $Y_iZ_i$ edges for $x_i$ literals (connecting each $Z_i$ to the $Y_i$ of the next instance of $x_i$), and another path from $P_n$ to $Q_n$ that passes through all of the $\neg x_i$ literals. Because the $X_i$ and $Y_i$ nodes are not available outside the $ABCDEF$ segments, these two full paths will be the only ways to get from $P_n$ to $Q_n$.
Finally add connecting edges from each $Q_n$ to $P_{n+1}$, from the last $F$ to $P_1$, etc.
Now a path that passes through everything in order and does not reuse edges will correspond to a satisfying truth assignment, with each variable's truth variable determined by the path from $P_n$ to $Q_n$ we don't take. And in each clause there must be at least one of the literals that have the right truth value.
