在无向无权图中缓存 BFS 遍历

Question

我有一个无向且未加权的图，其中包含大约一百万个节点 - 以矩阵格式可视化。

示例图的表示：

红细胞被阻塞。

我的问题是找到任意两个单元格之间的最短距离。源单元格和目标单元格将一一给出，我需要返回所有给定单元格对的最短路径。 遍历仅限曼哈顿（上，下，左，右 - 无对角线）。没有路径可以穿过被阻塞的单元格。

我看了以下内容：

• Floyd-warshall 算法：但它占用太多内存。
• Dijkstra算法对所有节点，但是太慢了
• A* 可以工作，但仍然会很慢 - 如果需要为所有对找到最短路径。

还有其他方法吗？

因为它只是一个均匀矩阵，我想可能有一些我不知道的模式。

能否以某种方式缓存 BFS 遍历，以便可以在已经访问过的节点处继续搜索而不是从头开始？

Answer 1

如果您的图形是 1000x1000 网格，则如果 x%100 = 0 或 y%100 = 0，则让每个单元格 (x,y) 成为“边界单元格”。

这将您的图形划分为 100 个由边界分隔的区域。

如果你需要在同一个区域内的点之间寻找一条最短路径，那么你可以只在区域内使用BFS，最多搜索10K个节点。

当你需要在不同区域之间寻找一条路径时，那么它总是包含一条到边界节点的路径，可能是一条边界节点之间的路径，然后是一条从边界节点到目标的路径。

您可以通过使用 Floyd-Warshall 预先计算每对边界单元之间的最短路径距离来加速搜索。只有大约 20000 个，因此这将需要存储大约 2 亿个长度。

然后，您的 BFS 搜索将仅限于源区域内的边、源区域和目标区域之间的 F-W 路径以及目标区域内的边。

这将为最坏情况的搜索提供 20-50 倍的加速。

Answer 2

由于您的顶点位于正交网格上，因此可以立即计算出两个单元格之间的“曼哈顿”路径。例如从 1,3 到 5,4 可以变成 1,3； 1,4; 2,4; 3,4; 4,4; 5,4.

因为没有路径可以通过阻塞的顶点：边走边检查，如果你碰到一个红色的、阻塞的单元格，改变正在改变的维度。

您的性能要求表明每次路径计算需要大约 1 毫秒（对于 20 分钟内的一百万条路径）。如果您可以使用曼哈顿路径，那可能才有可能，否则就不行。