使用Dijkstra算法的2d數組中的最短路徑？

Question

這是我第一次實現Dijkstra算法。好了，所以我在這裏有一個簡單的2D 9×9陣列：

的出發點是1，我們正在試圖讓任何綠化廣場。紅色方塊是牆壁或熔岩（無論滿足你的想象力）。

如何在Java中實現這個？

計算機科學是不是我的領域，因此我不是一個經驗豐富的程序員，所以我可能不知道該怎麼辦了一些堆棧推，僅循環和遞歸:(請保持輕鬆地和大家多多包涵！

Answer 1

這是similiar，應該讓你開始。但是，下面介紹的解決方案嘗試訪問右下角。您可以放鬆該條件，以找到底行。您還需要稍微更改編碼以具有表示此行的唯一值。

public class MazeSolver { 

    final static int TRIED = 2; 
    final static int PATH = 3; 

    // @formatter:off 
    private static int[][] GRID = { 
     { 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 }, 
     { 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1 }, 
     { 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 }, 
     { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1 }, 
     { 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 }, 
     { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, 
     { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
     { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } 
    }; 
    // @formatter:off 

    public static void main(String[] args) { 
     MazeSolver maze = new MazeSolver(GRID); 
     boolean solved = maze.solve(); 
     System.out.println("Solved: " + solved); 
     System.out.println(maze.toString()); 
    } 

    private int[][] grid; 
    private int height; 
    private int width; 

    private int[][] map; 

    public MazeSolver(int[][] grid) { 
     this.grid = grid; 
     this.height = grid.length; 
     this.width = grid[0].length; 

     this.map = new int[height][width]; 
    } 

    public boolean solve() { 
     return traverse(0,0); 
    } 

    private boolean traverse(int i, int j) { 
     if (!isValid(i,j)) { 
      return false; 
     } 

     if (isEnd(i, j)) { 
      map[i][j] = PATH; 
      return true; 
     } else { 
      map[i][j] = TRIED; 
     } 

     // North 
     if (traverse(i - 1, j)) { 
      map[i-1][j] = PATH; 
      return true; 
     } 
     // East 
     if (traverse(i, j + 1)) { 
      map[i][j + 1] = PATH; 
      return true; 
     } 
     // South 
     if (traverse(i + 1, j)) { 
      map[i + 1][j] = PATH; 
      return true; 
     } 
     // West 
     if (traverse(i, j - 1)) { 
      map[i][j - 1] = PATH; 
      return true; 
     } 

     return false; 
    } 

    private boolean isEnd(int i, int j) { 
     return i == height - 1 && j == width - 1; 
    } 

    private boolean isValid(int i, int j) { 
     if (inRange(i, j) && isOpen(i, j) && !isTried(i, j)) { 
      return true; 
     } 

     return false; 
    } 

    private boolean isOpen(int i, int j) { 
     return grid[i][j] == 1; 
    } 

    private boolean isTried(int i, int j) { 
     return map[i][j] == TRIED; 
    } 

    private boolean inRange(int i, int j) { 
     return inHeight(i) && inWidth(j); 
    } 

    private boolean inHeight(int i) { 
     return i >= 0 && i < height; 
    } 

    private boolean inWidth(int j) { 
     return j >= 0 && j < width; 
    } 

    public String toString() { 
     String s = ""; 
     for (int[] row : map) { 
      s += Arrays.toString(row) + "\n"; 
     } 

     return s; 
    } 

} 

Answer 2

我建議你從這裏開始寫下自然語言中應用dijkstras算法（假設你知道它的方法）的方法，然後開始將其轉換爲編程語言。

您將需要的基本問題回答爲：

• 節點是什麼？
• 什麼是連接？
• 每個連接的權重是多少？

一旦你這樣做了，你應該能夠找到一個（可能不是高效的）解決方案。

Answer 3

最佳的解決方案確實是使用Dijkstra或AStar的完成條件不同。所以，你需要寫if(targetNodes.contains(u)) break;代替if(target == u) break;

（參見維基百科：如果我們只在頂點源和目標之間的最短路徑感興趣，我們可以在第13行如果u =目標終止搜索）

這已經在我的項目中實現了......哦，這是作業;）？