找到網格上一個點和一行之間的最短路徑

Question

我知道有算法找到兩點之間的最短路徑，例如，在How to calculate the shortest path between two points in a grid中回答的算法。但是，現在，我有一個N * M網格，其中行從0到N-1，列從0到M-1，其中每個網格包含障礙物（或者您可以認爲它是兩個網格之間的距離）。例如，下面我有一個4×4格：

5 7 8 2 
2 7 4 3 
6 4 3 2 
5 7 2 5 

而且我想找到(0, 0)和(X, 3)，其中X可以是任意數量的左上角和底部行，即之間的最短距離從0到3.

我可以找到(0, 0) -> (0, 3)到(0, 0) -> (3, 3)之間的每條最短路徑，但這可能太慢了。這個問題是否有更有效的算法/方法？

Answer 1

這比您想象的要多得多，並且有一個很好的方法來解釋這一點。

你可以想象你的網格是一個圖。每個單元格都是一個節點，並且每個單元格與每個相鄰單元格之間具有相應的成本。

考慮將新節點添加到圖中，並將最後一行中的所有內容通過成本爲零的邊連接到新節點。現在，請考慮尋找從左上角到剛剛添加的魔術新節點的最短路徑。最短路徑將對應於通過網格的路徑，在最後一步，該路徑離開最後一行並進入該新節點。由於到新節點的邊的成本爲零，所以從左上角節點到這個新節點的最便宜路徑的成本是從左上角到最後一行中的任何單元的最佳路徑的成本。換句話說，如果可以解決一對節點之間的最短路徑問題，則可以解決從任何節點到圖中許多節點中的任何一個節點的最短路徑問題。

您能否看到一種方法來適應這種技術，以便您還可以找到第一行中的任何內容和最後一行中的任何內容之間的最短路徑？