查找與廣度的最短路徑節點首先搜索

Question

我運行廣度優先搜索的上圖找到Node 6從Node 0的最短路徑。

我的代碼

public List<Integer> shortestPathBFS(int startNode, int nodeToBeFound){ 
     boolean shortestPathFound = false; 
     Queue<Integer> queue = new LinkedList<Integer>(); 
     Set<Integer> visitedNodes = new HashSet<Integer>(); 
     List<Integer> shortestPath = new ArrayList<Integer>(); 
     queue.add(startNode); 
     shortestPath.add(startNode); 

     while (!queue.isEmpty()) { 
      int nextNode = queue.peek(); 
      shortestPathFound = (nextNode == nodeToBeFound) ? true : false; 
      if(shortestPathFound)break; 
      visitedNodes.add(nextNode); 
      System.out.println(queue); 
      Integer unvisitedNode = this.getUnvisitedNode(nextNode, visitedNodes); 

      if (unvisitedNode != null) { 
        queue.add(unvisitedNode); 
        visitedNodes.add(unvisitedNode); 
        shortestPath.add(nextNode); //Adding the previous node of the visited node 
        shortestPathFound = (unvisitedNode == nodeToBeFound) ? true : false; 
        if(shortestPathFound)break; 
       } else { 
        queue.poll(); 
       } 
     } 
     return shortestPath; 
    } 

我需要跟蹤的節點，通過它的BFS算法中。遍歷到達節點6，如[0,3,2,5,6]。爲此，我創建了一個名爲shortestPath &的列表，試圖存儲訪問節點的前一個節點，以獲取節點列表。 Referred

但它似乎沒有工作。最短路徑是[0,3,2,5,6]

在列表中我得到的是Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]

這是部分正確的，但給人的額外1。

如果我再次從shortestPath列表的第一個元素0開始&開始遍歷&回溯。像1沒有優勢3，所以我回去&從0移到3到5，我會得到答案，但不知道如果這是正確的方式。

獲得最短路徑節點的理想方式是什麼？

Answer 1

將所有訪問節點存儲在單個列表中對於找到最短路徑沒有幫助，因爲最終您無法知道哪些節點是導致目標節點的節點，哪些節點是死路一條。

你需要做的是爲每個節點存儲在從起始節點的路徑中的前一個節點。

因此，創建一個地圖Map<Integer, Integer> parentNodes，而不是這樣的：

shortestPath.add(nextNode); 

做到這一點：

parentNodes.put(unvisitedNode, nextNode); 

後到達目標節點，您可以遍歷地圖找路回到起始節點：

if(shortestPathFound) { 
    List<Integer> shortestPath = new ArrayList<>(); 
    Integer node = nodeToBeFound; 
    while(node != null) { 
     shortestPath.add(node) 
     node = parentNodes.get(node); 
    } 
    Collections.reverse(shortestPath); 
} 

Answer 2

除了我們已經給出的答案er3290797。

它看起來像你正在處理一個未加權的圖。我們將其解釋爲每條邊都有1的權重。在這種情況下，一旦將圖的每個節點（廣度優先遍歷）與根節點的距離關聯起來，重構從任意邊的任意最短路徑節點，甚至檢測是否有多個節點。

所有您需要做的是從目標節點開始的寬度（如果您希望每條最短路徑）或深度優先遍歷，並且只考慮深度值小於1的鄰居。因此我們需要從距離4（節點6）跳到3,2,1,0，並且只有一種方式（在這種情況下）這樣做。因此，我們需要從距離4（節點6）跳到3,2,1,0。

如果我們對節點4的最短路徑感興趣，結果將是距離2-1-0或節點4-3-0或4-8-0。

順便說一句，這種方法可以很容易地修改爲加權圖（也包含非負權重）：有效鄰居是那些距離等於電流減去邊的權重 - 這涉及一些實際計算，並直接沿着最短路徑存儲先前的節點可能會更好。

Answer 3

正如你可以在acheron55 answer看到：

「它具有非常有用的特性，如果所有的圖中的邊的未加權（或相同的重量），那麼一個節點訪問的第一個時間從源節點到該節點的最短路徑「

所以你所要做的就是跟蹤目標達到的路徑。 一個簡單的方法就是將用於到達節點的整個路徑推入Queue，而不是節點本身。
這樣做的好處是當達到目標時，隊列保存用於達到目標的路徑。
下面是一個簡單的實現：

/** 
* unlike common bfs implementation queue does not hold a nodes, but rather collections 
* of nodes. each collection represents the path through which a certain node has 
* been reached, the node being the last element in that collection 
*/ 
private Queue<List<Node>> queue; 

//a collection of visited nodes 
private Set<Node> visited; 

public boolean bfs(Node node) { 

    if(node == null){ return false; } 

    queue = new LinkedList<>(); //initialize queue 
    visited = new HashSet<>(); //initialize visited log 

    //a collection to hold the path through which a node has been reached 
    //the node it self is the last element in that collection 
    List<Node> pathToNode = new ArrayList<>(); 
    pathToNode.add(node); 

    queue.add(pathToNode); 

    while (! queue.isEmpty()) { 

     pathToNode = queue.poll(); 
     //get node (last element) from queue 
     node = pathToNode.get(pathToNode.size()-1); 

     if(isSolved(node)) { 
      //print path 
      System.out.println(pathToNode); 
      return true; 
     } 

     //loop over neighbors 
     for(Node nextNode : getNeighbors(node)){ 

      if(! isVisited(nextNode)) { 
       //create a new collection representing the path to nextNode 
       List<Node> pathToNextNode = new ArrayList<>(pathToNode); 
       pathToNextNode.add(nextNode); 
       queue.add(pathToNextNode); //add collection to the queue 
      } 
     } 
    } 

    return false; 
} 

private List<Node> getNeighbors(Node node) {/* TODO implement*/ return null;} 

private boolean isSolved(Node node) {/* TODO implement*/ return false;} 

private boolean isVisited(Node node) { 
    if(visited.contains(node)) { return true;} 
    visited.add(node); 
    return false; 
} 

這也適用於循環圖，其中一個節點可以有多個父。