已解決430363個問題，去搜搜看，總會有你想問的

在 2d 陣列中查找最短路徑

關注

首頁猿問在 2d 陣列中查找最短路徑

Java

青春有我 2022-08-17 17:09:14

我需要找到從左上角到右下角的最短路徑。規則是它必須從A到B到A到B等。例如，見圖片：上圖的預期輸出為 13。我試圖用一個dijkstra算法在java中實現這一點，但后來卡住了。這是正確的方法嗎？

查看完整描述

2 回答

三國紛爭

TA貢獻1804條經驗獲得超7個贊

如果目標是找到從左上角到右下角（或任何任意2點之間）的最短路徑，dijsktra是一種可能的方法，但是您必須從輸入正確構造圖形。

在這種情況下，我會選擇一個簡單的算法。您可以找到幾個在線資源來解釋它，包括此視頻或本文，因此我不會在此答案中詳細介紹。flood-fill

如果您正確實施了規則（僅 A 到 B 和 B 到 A），則可以僅使用 2 個矩陣（一個用于原始字母數組，一個用于距離）找到最短路徑。

反對回復 2022-08-17

富國滬深

TA貢獻1790條經驗獲得超9個贊

您可以使用任何圖形遍歷算法或任何尋路算法。T，這里有很多算法，如A *，Dijekstra，BFS，DFS ...

例如，讓我們以BFS為例，它查找圖形的2個節點之間的最短路徑。假設您的 2d 數組是一個圖形，如果 2 個節點之間的距離為 1 且其中一個節點為 A，第二個節點為 B https://en.wikipedia.org/wiki/Breadth-first_search，則邊緣處于狀態。)

只需從矩陣構造圖形并為圖形實現 BFS，或者您可以簡單地為數組實現 BFS。

反對回復 2022-08-17

關注

舉報

0/150

提交

取消