计算多个点之间的最短距离

Question

所以我有一个问题：我需要一个算法，给定坐标为(x;y)的一组n点，将所有点连接在一起的最短路径是什么，没有任何限制，这意味着一个点可以链接到任何数量的其他点。

解决这个问题的第一个想法是，对于每个未链接的点，找到最近的点并链接到它，然后从未链接点列表中删除这两个点，然后重新开始，直到没有更多未链接点为止。在此阶段，您已经创建了近点块。然后你把这些块连接起来，找到它们之间最短的距离。

这种方法的问题是1。它不给出最短路径2。这似乎效率很低，所以我问你，这种计算是什么类型的算法（我只需要点之间的总距离，我不在乎它们实际上是如何连接的）？

Answer 1

听起来好像可以使用生成树算法。在伪代码中：

build_tree(unconnected_nodes):
  connected_nodes = set()
  // pick a random unconnected node
  connected_nodes.add(unconnected_nodes.pop())
  while not empty(unconnected_nodes):
     best_connected_node = None
     best_unconnected_node = None
     shortest_distance = +Infinity
     for node1 in connected_nodes:
       for node2 in unconnected_nodes:
         if distance(node1, node2) < shortest_distance:
           shortest_distance = distance(node1, node2)
           best_unconnected_node = node2
           best_connected_node = node1
     connect(best_connected_node, best_unconnected_node)
     unconnected_nodes.remove(best_unconnected_node)
     connected_nodes(best_unconnected_node)
  return connected_nodes

这是假设你有一个本质上是全连通图的东西，通过"坐标"one_answers"无限制"，我认为这就是你所拥有的。如果没有，则需要遍历从连接节点到未连接节点的顶点集。

Answer 2

我认为您可以应用Prim的最短路径算法或Kruskal的最长路径算法。这些算法通常提供网络中两个不同节点之间的最短路径。对于您的问题，您可以将每个坐标对表示为一个顶点，并通过创建边的最小生成树来找到它们之间的最短路径。我正在写下面的伪代码：

mst = queue of all the result edges(or co-ordinates)
p =  queue of all the connected edges
while p is not empty
  edge e = min of p
  if union-find(both vertices of edge e)
    continue
  else
    union-find.add(both vertices of edge e)
    mst.add(e)

最后，您将有"mst"表示所有坐标之间的最短路径