從點列表中找到最短路徑

Question

如果我有一個從廣度優先搜索返回的點列表，它通過Java中的2D數組迷宮類型返回，我如何才能找到該列表中的最短路徑？例如，如果我的潛在目標點是[2,4]和[6,0]，並且我有一個到每個目標點的點列表，那麼我如何才能找出哪條路線最短？

我在想我可能不得不使用Djikstra的算法或某些東西，但我不確定。

非常感謝

Answer 1

您可以在這裏使用Dijkstra算法。鑑於你提到的陣列迷宮，第一步將是讓你的迷宮中的所有邊緣在2個相鄰節點之間，以及邊緣成本。對於節點，您需要知道每個節點是否已被訪問，以及訪問該節點的當前成本。

現在，如果你不關心獲得最短路徑，你可能不需要Dijkstra的。相反，您可以使用DP /遞歸方法來獲取從源座標到目標座標的可能路徑。如果你想看到Dijkstra的實現，this是我寫的東西。要獲得最短路徑，顯然需要節點之間的距離。

要找到2點之間的路徑，我會建議像this實施。它包括DP和遞歸實現，並比較兩者的運行時間（對於大型數據集，遞歸可能需要很長時間才能運行）。

我覺得這應該足以讓你開始。讓我知道你是否需要其他信息。

Answer 2

我並沒有最終使用Dijkstra's，而是改變了我的廣度優先搜索，以便從原點開始添加一個「級別」值或「距離」值，該值將與每個訪問節點向上計數。如果路徑已經分支，計數將保持一致，並且由於我已經知道了終點，所需要的只是檢查我的終點中的「計數」是什麼並且進行比較。

儘管謝謝你的幫助！如果網站允許我，您會收到一個贊成票。

對於那些面臨類似問題的人： 我做了一個名爲PointC的簡單類，它繼承自Point，但增加了一個「count」值。在廣度優先搜索的每一步中都適當地更新了計數，然後在最後比較終點以獲得最優路徑。