I have been pondering this question for a little while and my colleagues seem unsure as well.
The problem involves a vehicle that must visit several waypoints contained in a large road network. The optimal route visits each waypoint in some sequence from the vehicle's starting position S. The ending position does not matter.
Assume there are 5 waypoints and I've used the A* algorithm and by brute force, have found the optimal route to visit all of them from S. The optimal, shortest route is SABCDE. However, I am now told an additional waypoint X needs to be added somewhere along this route and this new route must also be of optimal length. My question is, given SABCDE is optimal, will the optimal solution incorporating X only require a single route to be diverted via X, or X being appended to the end. Will the most optimal route be one of: SXABCDE, SAXBCDE, SABXCDE, SABCXDE, SABCDXE or SABCDEX? Or, is this not guarenteed to be the case, meaning the optimal solution might be SACXDEB?