Graph Problem: find X path lengths which are closest to each other (similar to shortest path)

Question

I have the following problem:

1 Start point 1 End point 7 Knots / waypoints which you have to visit in any order

All 9 knots are connected with each other. All paths have to start at the start point and end at the end point. All paths have to visit all 7 points in any order exactly once.

Now I need to find x individual paths which are the shortest connections and also the closest to each other in terms of length. (e.g. the shortest path would be 10 but is not chosen because 3 paths are 22, 21, 20 long).

Another restriction is, that each path can only visit knots/wayponints where no other path is at the moment. So every knot has a capability of 1 for the same step e.g. if I am looking for 5 paths which are shortest and closest together in terms of length, at the second step after the start point, just one path of the five can be at know number 1, etc.

How can I solve this problem? Best in Excel, Python or R

Thanks!

Answer 1

Brute force.

Your problem starts at start and ends at end. In Python (see this answer on Stack Overflow) use itertools.combinations(iterable, r) to get all sequence permutations, and just compute the length of each path.

Then sort the paths by length, and for each term of the (path, length) data after the first one, $(p_i,l_i)_{i=1}^{5!-1}$ (assuming zero-based arrays), store also sum of distances with previous and next element, i.e. $$ (p_i,l_{i-1} + l_i + l_{i+1})_{i=1}^{5!-1} $$ and pick the smallest element in that new data set.

Your last condition for the 3 paths can be enforced here by eliminating $p_i$ element if $p_{i-1},p_i,p_{i+1}$ do not satisfy whatever condition you like...