假设我有一个N*N 2D网格，该网格具有加权的边缘。我在网格上所做的每个移动都具有始终具有固定的X或Y分量的约束，即：在every移动中，我have在X坐标中移动1个单位，在Y坐标中移动3个单位坐标。
我曾考虑过去除边缘不应该走动，但是这并不能解决我必须做这些动作的事实。如何修改dijkstra（或任何寻路算法，但最好是dijkstra），使其在这些约束下为我提供从A到B的最短路径？
我知道已经有很长时间了，但是我想提供关于这个问题的观点，因为还没有一个具体的答案。
由于在遍历网格时受到限制（类似于您必须以（1,3）的矢量进行移动的示例，即在X方向上为1，在Y方向上为3），因此仅许多单元格都是可及的，它们将构成图形，在该图形上我们将执行Dijkstra算法。我们可以在原始网格本身上执行Dijkstra，并且无法访问的节点到源的距离将是无限的。但是，这非常昂贵，因为我们正在有效地增加算法每次迭代中必须检查的像元数量。
我们可以通过执行修改后的BFS来计算所有可达小区的图。在搜索的每次迭代中，将仅检查有效单元格。这里的“有效”表示它们满足遍历约束并且位于原始网格的范围内。例如，如果我们使用从（0,0）开始的非负数索引6x6网格中的所有像元，并且约束为（1,2），则如果对像元（0,0）执行BFS，则只有有效邻居是（1,2）。然后，BFS将通过选择以下两种可能的路线中成本较低的一条来计算连接（0,0）和（1,2）的边的权重：（0,0）->（0,1）->（1， 1）->（1,2）和（0,0）->（0,1）->（0,2）->（1,2）。像常规BFS一样，对（0,0）的所有邻居执行此操作，然后对所有邻居及其邻居执行此操作，依此类推。区别在于，在BFS迭代期间，当遇到已经发现的单元时，仍会计算该单元与BFS中正在迭代的单元之间的边缘权重（因为我们正在制作一个图，其中包含所有可能的有效连接可达的单元，而不仅仅是BFS树）。最后，我们将创建所需的图形。
如果最终目标不在结果图中（我们可以拥有一个跟踪图中所有单元格的集合），那么我们得出结论，从源到目标没有路径。
如果目的地在图中，则我们在图中正常执行Dijkstra的算法。结果将是最短的路径。