最短路徑沒有對角線移動

Question

我知道有很多最短路徑算法，但我想問是否有任何修改可以做，使一些算法像*或Dijkstra選擇最短路徑，但沒有對角線移動如此和

下來，左，右是允許移動

Answer 1

你可能想的算法是A *（如果你想在大地圖與一些連貫的障礙很短的路徑），雖然你可能只需要Dijkstra的（如果你必須有數學上最短的路徑，或者地圖與任何物理物體沒有任何真正的關係）。如果您使用曼哈頓距離作爲A *的啓發式，您只需禁止對角線移動即可獲得更好的結果。對於Dijkstra的圖，圖沒有對角線鏈接。