Shortest path touching all points

Question

I am looking for a solution to derive the shortest route that touches all the points using Python. Please note that

1. This is not a Travelling salesman problem (TSP), in which the route should end where it started (salesman reaches his origin point).
2. No need to consider the road availability or any such parameters.

I have tried TSP solution that makes a circular path instead of the shortest path. Also, I tried routing-py that considers the road network and finds the optimal road route rather than the shortest path. I am looking for the shortest route that can start from any point, end at any point, and touches all the points.

Can you provide any suggestions in terms of code/ theoretical possibility?

Consider the code below as the input points.

import random
from shapely.geometry import Point
import matplotlib.pyplot as plt

minx, miny, maxx, maxy = 100, 500, 200, 600
ptList = []
for _ in range(50):
    pnt = Point(random.uniform(minx, maxx), random.uniform(miny, maxy))
    ptList.append(pnt)

xs = [point.x for point in ptList]
ys = [point.y for point in ptList]
plt.scatter(xs, ys)

I also tried TSP without the last point and it didn't help. The derived route isn't efficient since it moves in one direction and comes back in the same direction, making the route longer. The image below represents that scenario.

Got an update! I understand that what I am looking for is termed 'shortest Hamilton path'. It is a modified TSP algorithm, in which the cyclic coming back is not forced. I got a solution using it, and below is the code. However, the result is not effective in a few nodes. The misrouting is marked in black circles in the figure below. Correcting this misrouting could provide a better solution to this kind of problem in terms of hardcoding, speed, and effectiveness.

import networkx as nx
g = nx.Graph()
# A distance matrix is made that have distance btwn each points
# A loop that creates all the edges  
for i in range(len(distance_matrix)):
    source = i
    curr_pt_dist = distance_matrix[i]
    for j in range(len(curr_pt_dist)):
        dest = j 
        # eucl -> Distance btwn source and destination point
        eucl = curr_pt_dist[j]   
        g.add_edge(source, dest, weight = eucl)
# Finding the route
solved_path = nx.approximation.traveling_salesman_problem(g, weight='weight', cycle=False)
# Getting the points in the calculated order and ploting them as lines.
path = []
for item in solved_path:
    path.append(ptList[item])
route_polyline = LineString([z for z in path])
route_geo = gpd.GeoSeries(route_polyline)
route_geo.plot

Answer 1

This is a python codebase which tries to draw the shortest network possible connecting points: https://github.com/facebookresearch/many-to-many-dijkstra

The only limitation is that the output will be a raster, so you will have to vectorize the output into lines.

Answer 2

I have not enough reputation to comment, so I will give you my idea as an answer :

Beware the wheel

I think that everytime you try to re invent the wheel nowadays it is not because it does not exist, but because you do not know it exists. What I propose here is kind of re inventing the wheel so... just a warning regarding my own idea.

The idea

1. Perform a Delaunay triangulation. I think it is a good start as it preserves local relationship between points.

2. Choose a starting point

3. Then travel the points cloud by shortest path among the remaining direct connected points (you'll have to track what points are already in the path so that you do not connect a point twice).You will obviously forget some points this way.

4. Wherever you forget a point, find the closest connected point and redirect one connection to join him

The issues I see : this is not THE shortest path to travel through all the points. More precisely, this method depends on the starting point. But if you have a small amount of points, it should be quick to test all starting points and find the shortest solution overall.
There might also be issues regarding forgotten "islands" of points. This could happen if your points are spread in groups. In that case you could:

1. simplify the point cloud by clustering (you link an island of points to a virtual center point obtained by clustering)

2. you perform the preceding method per island and then on the simplified point cloud.