首頁(yè) 猿問(wèn) 在 2d 陣列中查找最短路徑

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

Java

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

我需要找到從左上角到右下角的最短路徑。規(guī)則是它必須從A到B到A到B等。例如，見(jiàn)圖片：上圖的預(yù)期輸出為 13。我試圖用一個(gè)dijkstra算法在java中實(shí)現(xiàn)這一點(diǎn)，但后來(lái)卡住了。這是正確的方法嗎？

查看完整描述

2 回答

三國(guó)紛爭(zhēng)

TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超7個(gè)贊

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

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

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

反對(duì) 回復(fù) 2022-08-17

富國(guó)滬深

TA貢獻(xiàn)1790條經(jīng)驗(yàn) 獲得超9個(gè)贊

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

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

只需從矩陣構(gòu)造圖形并為圖形實(shí)現(xiàn) BFS，或者您可以簡(jiǎn)單地為數(shù)組實(shí)現(xiàn) BFS。

反對(duì) 回復(fù) 2022-08-17