algorithm - 边到边推荐的最短路径算法

Question

我有一个移动应用程序的棋盘游戏，显示在这个链接中:http://i45.tinypic.com/23u8u1h.png

起点可以是任何单元格。获胜者是垂直(绿色玩家)或水平(红色玩家)连接他/她的人。

节点是彩色单元格。白细胞可以被认为是重量吗？我不确定如何实现它，但当我想到 Dijkstra 算法时，我相信当板处于这种状态时，它会花费大量时间来计算直到它得出正确答案:http://i50.tinypic.com/35ivofd.png (我必须将算法应用于那四个绿色单元格)

我想要一个算法来告诉我“http://i48.tinypic.com/28c2ijl.png”黑色、棕色、蓝色和紫色路径是合理时间内最短的路径。

提前致谢。

Answer 1

我认为 Dijkstra 在这里工作得很好，尤其是与 Union Find algorithm 结合使用时用于连接彼此相邻的字段并填充白色以外的颜色。通往白场的边成本为 1，通往自己场的边成本为 0，而通往敌方场的边成本为无穷大(例如 mn)。然后，您不会在代表单个字段的节点上运行 Dijkstra，而是在这些字段的联合(非白色字段的集群)上运行。

Dijkstra 将在这里工作大约 O(mn log^2(mn))，其中 n 和 m 是电路板的尺寸, 并且 Union Find 将在 O(log mn) 时间内通过简单的优化工作，如链接文章底部所述。