二進制矩陣的兩點之間的最短路徑

-1

我想查找二進制矩陣的兩點之間的最短路徑。二進制矩陣的兩點之間的最短路徑

矩陣的來源和目標由用戶給出。我們只能選擇在矩陣中爲1的位置，並且還可以向下對角線，向左，向右移動&。

如果移動是對角的，則成本爲root 2，否則爲1.所以我想要一個算法如何找到它。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm – 2013-02-14 07:05:56

首先從矩陣生成一個_graph_。提示：它在每個水平/垂直相鄰的單元格之間有一個邊，權重爲1，每個對角線相鄰的單元格之間的邊爲sqrt（2）。然後申請Dijkstra。 – 2013-02-15 14:03:03

您正在尋找的是單一來源最短路徑算法，這意味着您選擇圖中的源節點（例如）並找到最短的全部或一個節點。幾種算法用於此目的的存在 -

我的建議是你讀了這些，並選擇一個適合你的目的。

2013-02-14 07:14:21 Cygnus

Bellman Ford通常不用於具有正邊緣的圖形，因爲它的表現比Dijkstra算法要差。 Floyd Warshall都是最短路徑 - 如果在同一個圖上有很多查詢，那麼這個路徑很好。 – nhahtdh 2013-02-14 08:36:41

我已經讀出了所有這些算法，但是因爲我的矩陣非常大，比如400 * 400，所以應用這些算法相當困難。由於上述算法無法確定對角距離。 – 2013-02-14 09:11:46

PLZ幫助我一些...我需要的算法和C代碼將採取二進制矩陣（400 * 400）作爲文件，源和目標軸給出用戶假設（S = 60,9＆D = 400,300）並找到它們之間的最短路徑，如果對角移動，則花費根目錄2，否則爲1 – 2013-02-14 10:39:02

回答