找出GPS坐标集之间的最短距离

1条回答

网友

1楼 · 发布于 2024-09-28 21:30:31

最好的方法是创建一个图。如果您不知道这是什么，您应该查找它，因为它是一个非常重要的数据结构。您可能还需要知道要完全理解以下代码是什么。Python没有内置的图形，因此您需要创建自己的图形。你知道吗

您需要的图形类型是一个无向加权图，其中所有节点或GPS坐标相互连接。然后，您可以使用“Dijkstra算法”的形式对图形进行排序，以找到到所有点的最短路径。你知道吗

下面是您所寻找的实现。不过，我将其编码为使用包含成对坐标列表的列表。它还包括一个驱动程序driver（），您可以调用来测试它。你知道吗

我写得很快，并没有把它作为一个类来编写，但在现实世界中，你绝对应该这样做。你知道吗

请注意，当您运行driver函数时，它将执行代码并打印出所提供坐标列表的所有可能路径及其权重。”在你的例子中，“重量”指的是两个点之间的距离。打印的列表显示了它所走的路径，其中“1”表示坐标列表索引“0”处的一对点。列表中的下一个数字是它下一个指向的点对。你知道吗

如果您还有任何问题，请随时询问

from collections import defaultdict
from math import sqrt

# Shortest path to all coordinates from any node
# Coordinates must be provided as a list containing lists of
# x/y pairs. ie [[23.2321, 58.3123], [x.xxx, y.yyy]]


def distance_between_coords(x1, y1, x2, y2):
    distance = sqrt(((x2 - x1) ** 2) + ((y2 - y1) ** 2))
    return distance


# Adds "names" to coordinates to use as keys for edge detection
def name_coords(coords):
    coord_count = 0
    for coord in coords:
        coord_count += 1
        coord.append(coord_count)
    return coords


# Creates a weighted and undirected graph
# Returns named coordinates and their connected edges as a dictonary
def graph(coords):
    coords = name_coords(coords)
    graph = defaultdict(list)
    edges = {}
    for current in coords:
        for comparer in coords:
            if comparer == current:
                continue
            else:
                weight = distance_between_coords(current[0], current[1],
                                                 comparer[0], comparer[1])
                graph[current[2]].append(comparer[2])
                edges[current[2], comparer[2]] = weight
    return coords, edges


# Returns a path to all nodes with least weight as a list of names
# from a specific node
def shortest_path(node_list, edges, start):
    neighbor = 0
    unvisited = []
    visited = []
    total_weight = 0
    current_node = start
    for node in node_list:
        if node[2] == start:
            visited.append(start)
        else:
            unvisited.append(node[2])
    while unvisited:
        for index, neighbor in enumerate(unvisited):
            if index == 0:
                current_weight = edges[start, neighbor]
                current_node = neighbor
            elif edges[start, neighbor] < current_weight:
                current_weight = edges[start, neighbor]
                current_node = neighbor
        total_weight += current_weight
        unvisited.remove(current_node)
        visited.append(current_node)
    return visited, total_weight


def driver():
    coords = [[1.7592675, 92.4836507], [17.549836, 32.457398],
              [23.465896, 45], [25.195462, 37.462742],
              [42.925274, 63.234028], [2.484631, 5.364871],
              [50.748376, 36.194797]]
    coords, edges = graph(coords)
    shortest_path(coords, edges, 3)
    shortest_path_taken = []
    shortest_path_weight = 0

    for index, node in enumerate(coords):
        path, weight = shortest_path(coords, edges, index + 1)
        print('                   ')
        print("Path", index + 1, "=", path)
        print("Weight =", weight)
        if index == 0:
            shortest_path_weight = weight
            shortest_path_taken = path
        elif weight < shortest_path_weight:
            shortest_path_weight = weight
            shortest_path_taken = path
    print('                   ')
    print("The shortest path to all nodes is:", shortest_path_taken)
    print("The weight of the path is:", shortest_path_weight)

编辑：以下是调用驱动程序函数时的输出：

                   
Path 1 = [1, 5, 3, 4, 2, 7, 6]
Weight = 386.3252849770695
                   
Path 2 = [2, 4, 3, 6, 7, 5, 1]
Weight = 189.3710721663407
                   
Path 3 = [3, 4, 2, 5, 7, 6, 1]
Weight = 173.99235180101968
                   
Path 4 = [4, 3, 2, 7, 5, 6, 1]
Weight = 172.86112533927678
                   
Path 5 = [5, 3, 7, 4, 2, 1, 6]
Weight = 247.08415835699554
                   
Path 6 = [6, 2, 4, 3, 7, 5, 1]
Weight = 330.1567215845902
                   
Path 7 = [7, 4, 5, 3, 2, 6, 1]
Weight = 247.70066871941674
                   
The shortest path to all nodes is: [4, 3, 2, 7, 5, 6, 1]
The weight of the path is: 172.86112533927678
[Finished in 0.1s]*

相关问题更多 >

编程相关推荐

热门问题

热门文章