c++ - 使用坐标开发距离矩阵

Question

嘿，我遇到了一个问题，我基本上得到了一张任意大小的网格纸，并且必须仅使用页面上每个网格点的坐标来开发距离矩阵。

我认为最好的方法是用于最短路径对的 Floyd-Warshall 或 Djikstra 算法，但不知道如何使其适应坐标距离，因为所有文档都使用预先确定的距离矩阵。所以任何帮助都会很重要

Answer 1

距离矩阵仅包含到所有其他点的距离。

基本上，您只需要使用适当的度量来计算距离。如果你想要“正常”距离，它是 sqrt((x1-x2)^2+(y1-y2)^2) 其中 (x/y) 是以毫米/英寸为单位的点的坐标。如果您想要纸上的距离，只需遵循 |x1-x2|+|y1-y2| 的行。除非你在纸上有墙壁，否则图形算法将是一种过度杀伤力。