计算网格中点组合之间的距离

Question

我正在寻找以下问题的有效解决方案。这应该适用于python，但不一定是在python。

我有一个2D矩阵，矩阵的每个元素代表2D正交网格中的一个点。我想计算网格中几对点之间的最短距离。如果网格中没有“障碍”，这将是微不足道的。

一个数字有助于解释：

图中的每个单元格是矩阵的一个元素（矩阵是正方形，但它可以是矩形）。灰色细胞是障碍物，两点之间的任何路径都必须绕过它们。绿色细胞是我感兴趣的细胞。我对红细胞不感兴趣，但是一条路可以通过它们。

像A和B这样的点之间的距离很难计算，但如何计算A和C之间的路径，如图所示？

我读过关于A* algorithm的内容，但由于我正在使用一个相当大的网格，一般（几百）x（几百），我想知道是否有更聪明的选择。请记住：我必须找到所有“绿色细胞”之间的距离，而不仅仅是两个之间的距离。如果我有n个绿色单元格，我将有许多等于二项式系数（n 2）的组合。

网格是固定的，我必须计算所有距离一次，然后在进一步的计算中使用它们，比如根据矩阵中的相关索引访问它们。

注意：问题不是this one，坐标是在列表中。我的2D坐标是在2D网格中组织的，问题是利用这个方面来获得更有效的算法。

Answer 1

我想最直接的解决方案是Floyd-Warshall算法，它计算图形中所有节点对之间的最短距离。这并不一定会利用您碰巧拥有2D网格的事实（它也可以在其他类型的图形上工作），但它应该可以正常工作。您拥有2D网格的事实可能使您能够比为任何任意图形编写实现更有效地实现它（例如，您可以在矩阵中计算距离，而不是效率低一些数据结构）。

常规版本仅生成所有最短路径的距离作为输出，并且实际上不将路径本身存储为输出。维基百科页面上有关于如何修改算法的其他信息，以便您在必要时有效地重建路径。

直觉上，我怀疑更有效的实现可能会利用你有2D网格的事实，可能使用来自Rectangular Symmetry Reduction和/或Jump Point Search的想法。这两个想法传统上都与A *一起用于单对寻路查询，但我不知道有任何工作将它们用于所有对最短路径计算。我的直觉说他们也可以在那里被利用，但是在准确地弄清楚并正确实现它的时候，你可以更容易地实现和运行Floyd-Warshall。