python - 我有 4 点，我想找到给定起点的最短路径

Question

x1 = 7
y1 = 5
x2 = 8
y2 = 7
x3 = 12
y3 = 9
x4 = 13
y4 = 12

import math

d1 = math.sqrt(x2 - x1)**2 + (y2 - y1)**2
d2 = math.sqrt(x3 - x1)**2 + (y3 - y1)**2
d3 = math.sqrt(x4 - x1)**2 + (y4 - y1)**2
d4 = math.sqrt(x3 - x2)**2 + (y3 - y2)**2
d5 = math.sqrt(x4 - x2)**2 + (y4 - y2)**2
d6 = math.sqrt(x4 - x3)**2 + (y4 - y3)**2
distances = [(d1 + d5 + d6 + d2), (d3 + d6 + d4 + d1)]

print(f"the shortest path is {min(distances)} cm and the longest path is {max(distances)} cm")

通过这样做，我将起点设置为X1, Y1，并且我基本上将这些点连接起来。x1,y1但是，如果我需要找到通过n点的距离怎么办，x1 y1这是给定的。我应该怎么做才能优化流程？谢谢你。

标签： python

Answer 1

优化是使用带堆的 Prim 算法

代码

from heapq import heappush, heappop

def find_min_path(points):
    '''
        min path starting at points[0] using Prim's heap based algorithm
    '''
    def distance(p1, p2):
        ' Distance between two points in 2D '
        d = (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2
        return d**0.5
    
    h = []                 # Empy heap
    path = [points[0]]     # Add first point to path
    heappush(h, (0, path)) # Add to heap tuple of (distance, path)

    while h:
        # Expand path with smallest total distance
        d, path = heappop(h)

        if len(path) == len(points):
            # Completed path
            break

        for p in points[1:]:   
            # for all points not in starting point
            if not p in path:
                # Extend if point p not in path
                # distance increases by distance to last point in path to p
                # path extended by p
                heappush(h, (d + distance(p, path[-1]), path + [p]))
                
    return d, path

测试

# List of 2D points
points = [(7, 5), (8, 7), (12, 9), (13, 12)]

d, path = find_min_path(points)
print(f'Min Distance {d:.4f} using path {*path,}')

输出

Min Distance 9.8705 using path ((7, 5), (8, 7), (12, 9), (13, 12))