假设我有一个带加权边的二维网格。我在网格上做的每一个移动都有一个固定的X或Y分量的约束，即：在每一个移动中，我必须在X坐标系中移动1个单位，在Y坐标系中移动3个单位。
我想去掉我不应该穿过的边缘，但这并不能说明我必须做这些动作。如何修改dijkstra（或任何寻路算法，但最好是dijkstra），以便在这些约束条件下，它为我提供从a到b的最短路径？
最佳答案
我知道已经很长时间了，但我只想提供我对这个问题的看法，因为还没有一个具体的答案。
因为在遍历网格时有一个约束（类似于你必须以向量（1,3）移动的例子，即1在x方向，3在y方向），当给定一个起点时，只有一些单元格是可以到达的，它们将形成一个图形，我们将在这个图上执行dijkstra的算法。我们可以在原始网格上执行dijkstra，无法到达的节点将与源节点有无限的距离。然而，这是非常昂贵的，因为我们正在有效地增加我们必须在算法的每次迭代中检查的单元数。
我们可以通过执行一个修改的bfs来计算所有可到达单元的图。在每次搜索迭代中，只检查有效单元格。”这里的“valid”表示它们满足遍历约束，并且它们位于原始网格的范围内。例如，如果我们使用从（0,0）开始的非负数索引6x6网格中的所有单元格，并且约束为（1,2），那么如果对单元格（0,0）执行bfs，则唯一有效的邻居将是（1,2）。然后，BFS将通过选择两个可能路线中成本较低的路线（0,0）—>（0,1）—>（1,1）—>（1,2）和（0,0）—>（0,1）—>（0,2）—>（1,2）来计算边缘连接（0,0）和（1,2）的重量对（0，0）的所有邻居执行此操作，然后对所有邻居及其邻居执行此操作，依此类推，就像常规的bfs一样。区别在于，在bfs迭代过程中，当遇到已发现的单元格时，仍会计算该单元格与在bfs中迭代的单元格之间的边权重（因为我们正在生成一个图，其中包含可到达单元格之间的所有可能和有效的连接，而不仅仅是bfs树）。最后，我们将创建所需的图形。
如果最终目的地不在结果图中（我们可以有一个集合来跟踪图中的所有单元格），那么我们就得出结论，从源到目的地没有路径。
如果目的地在图中，那么我们在图上正常地执行dijkstra算法。结果将是最短的路径。
关于algorithm - 具有强制运动约束的Dijkstra，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37277673/