使用鄰接矩陣在迷宮圖中找到最短路徑

我在解決迷宮圖中找到最短路徑的特定問題時遇到了一些麻煩。可能是因爲迷宮由四維數組初始化這一事實而被阻塞，如 adjacent = new boolean[height][width][height][width]; 第一對和第二對索引以行/列形式指定圖中的位置。該圖是這樣的：使用鄰接矩陣在迷宮圖中找到最短路徑

XXXXXXXXXXXXX 
..........X.X 
X.XXX.XXX.X.X 
X.X.X...X.X.X 
X.X.XXX.XXX.X 
X...X.....X.. 
XXXXXXXXXXXXX

ArrayList中必須持有頂點的位置的路徑，以便從開始到結束的包容性。

我已經寫過構造函數和連接方法;然而，我發現最短路徑方法的麻煩。下面是如何創建的迷宮圖表的例子：

final int edges[][] = {{1, 0, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 1}, 
       {1, 2, 1, 3}, {1, 3, 1, 4}, {1, 4, 1, 5}, {1, 5, 1, 6}, 
       {1, 5, 2, 5}, {1, 6, 1, 7}, {1, 7, 1, 8}, {1, 8, 1, 9}, 
       {1, 9, 2, 9}, {1, 11, 2, 11}, {2, 1, 3, 1}, {2, 5, 3, 5}, 
       {2, 9, 3, 9}, {2, 11, 3, 11}, {3, 1, 4, 1}, {3, 3, 4, 3}, 
       {3, 5, 3, 6}, {3, 6, 3, 7}, {3, 7, 4, 7}, {3, 11, 4, 11}, 
       {4, 1, 5, 1}, {4, 3, 5, 3}, {4, 7, 5, 7}, {4, 11, 5, 11}, 
       {5, 1, 5, 2}, {5, 2, 5, 3}, {5, 5, 5, 6}, {5, 6, 5, 7}, 
       {5, 7, 5, 8}, {5, 8, 5, 9}, {5, 11, 5, 12}}; 

     MazeGraph maze = new MazeGraph(13, 7); 

     for (int[] edge : edges) 
      maze.connect(new Location(edge[0], edge[1]), new Location(edge[2], edge[3]));

來源

2015-05-31 Levi

你有沒有聽說過* Dijkstra的算法*？ –

首先，這

adjacent = new boolean[height][width][height][width];

與此相矛盾：

的第一和第二對索引的指定行/列形成圖中的位置。

它是列/行，而不是行/列。

Dijkstra's algorithm應該爲您的矩陣實施。報價：

讓我們開始的節點被稱爲初始節點。假設節點Y的距離是從初始節點到Y的距離。 Dijkstra的算法將分配一些初始距離值，並且試圖逐步改進它們。

分配到每一個節點的暫行距離值：它設置爲零我們最初的節點和無窮大的所有其他節點。

將初始節點設置爲當前。標記所有其他未訪問的節點。創建一組所有未訪問節點，稱爲未訪問集。

當前節點，考慮其所有未訪問的鄰居並計算它們的暫行距離。將新計算的暫定距離與當前分配值進行比較，並將指定爲較小值。例如，如果當前節點A被標記爲距離6，並且將其與鄰居B連接的邊緣的長度爲 2，則到B（通過A）的距離將是6 + 2 = 8。如果B先前用大於8的距離標記了，然後將其更改爲8. 否則，保持當前值。

當我們完成考慮當前節點的所有鄰居時，將當前節點標記爲已訪問並將其從未訪問集合中移除。被訪問的節點將不會再次被檢查。

如果目的地節點已被標記訪問（規劃兩個特定節點之間的路由時），或者如果在未訪問的集合中的節點之間的最小暫定距離爲無窮大時（當規劃完整遍歷;還有時發生在初始節點和其餘未訪問節點之間沒有連接），然後停止。該算法已完成。

否則，選擇標有最小的暫行距離未訪問節點，將其設置爲新的「當前節點」，並進入回到步驟3

來源

2015-05-31 14:01:29

使用鄰接矩陣在迷宮圖中找到最短路徑

回答

相關問題