我正在寻找以下问题的有效解决方案。这应该适用于 python，但不必在 python 中。
我有一个二维矩阵，矩阵的每个元素代表二维正交网格中的一个点。我想计算网格中两点之间的最短距离。如果网格中没有“障碍”，这将是微不足道的。
一个数字可以帮助解释:
图中的每个单元格都是矩阵的一个元素(矩阵是正方形，但也可以是矩形)。 灰色单元格是障碍物，两点之间的任何路径都必须绕过它们。 绿色细胞是我感兴趣的细胞。我对红色细胞不感兴趣，但一条路径可以穿过它们。
像A和B这样的点之间的距离计算起来很简单，但是如何计算如图所示的A和C之间的路径呢？
我已阅读有关 A* algorithm 的内容，但由于我正在使用一个相当大的网格，通常是(几百)x(几百)，我想知道是否有更聪明的替代方案。请记住:我必须找到所有“绿色单元”对之间的距离，而不仅仅是其中两个之间的距离。如果我有 n 个绿色单元格，我将有许多等于二项式系数 (n 2) 的组合。
网格是固定的，我必须计算一次所有距离，然后将它们用于进一步的计算，比如根据矩阵中的相关索引访问它们。
注意:问题不是 this one ，坐标位于列表中。我的 2D 坐标是在 2D 网格中组织的，问题是如何利用这一方面来获得更有效的算法。
最佳答案
我认为最直接的解决方案是 Floyd-Warshall算法，计算图中所有节点对之间的最短距离。这不一定利用您碰巧有一个 2D 网格这一事实(它也可以在其他类型的图形上工作)，但它应该可以正常工作。事实上，您确实有一个 2D 网格，这可能使您能够比为任何任意图编写实现更有效地实现它(例如，您可以只存储在矩阵中计算的距离，而不是存储一些效率较低的数据)数据结构)。
常规版本仅生成所有最短路径的距离作为输出，并且实际上并不将路径本身存储为输出。维基百科页面上有关于如何修改算法以使您能够在必要时有效地重建路径的其他信息。
直觉上，我怀疑可能会利用二维网格这一事实，实现更高效的实现，可能使用 Rectangular Symmetry Reduction 中的想法。和/或Jump Point Search 。这两个想法传统上都与 A* 一起用于单对寻路查询，但我不知道有任何使用它们进行全对最短路径计算的工作。我的直觉表明它们也可以在那里被利用，但是当需要准确地弄清楚并正确实现它时，您可能可以更轻松地实现和运行 Floyd-Warshall。
关于python - 计算网格中点组合之间的距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47835123/