未加權圖的最短路徑（最少節點）

Question

我正在嘗試構建一個方法，該方法返回未加權圖中從一個節點到另一個節點的最短路徑。我考慮過使用Dijkstra's，但這似乎有點矯枉過正，因爲我只需要一對。相反，我實施了廣度優先搜索，但麻煩的是，我的返回列表包含一些我不想要的節點 - 我如何修改我的代碼以實現我的目標？

public List<Node> getDirections(Node start, Node finish){ 
    List<Node> directions = new LinkedList<Node>(); 
    Queue<Node> q = new LinkedList<Node>(); 
    Node current = start; 
    q.add(current); 
    while(!q.isEmpty()){ 
     current = q.remove(); 
     directions.add(current); 
     if (current.equals(finish)){ 
      break; 
     }else{ 
      for(Node node : current.getOutNodes()){ 
       if(!q.contains(node)){ 
        q.add(node); 
       } 
      } 
     } 
    } 
    if (!current.equals(finish)){ 
     System.out.println("can't reach destination"); 
    } 
    return directions; 
} 

Answer 1

實際上，您的代碼不會在循環圖中完成，請考慮圖1 - > 2 - > 1.您必須有一些數組，您可以在其中標記已經訪問過哪個節點。而且對於每個節點，您可以保存之前從其來的節點。所以這裏是正確的代碼：

 
private Map<Node, Boolean>> vis = new HashMap<Node, Boolean>(); 

private Map<Node, Node> prev = new HashMap<Node, Node>(); 

public List getDirections(Node start, Node finish){ 
    List directions = new LinkedList(); 
    Queue q = new LinkedList(); 
    Node current = start; 
    q.add(current); 
    vis.put(current, true); 
    while(!q.isEmpty()){ 
     current = q.remove(); 
     if (current.equals(finish)){ 
      break; 
     }else{ 
      for(Node node : current.getOutNodes()){ 
       if(!vis.contains(node)){ 
        q.add(node); 
        vis.put(node, true); 
        prev.put(node, current); 
       } 
      } 
     } 
    } 
    if (!current.equals(finish)){ 
     System.out.println("can't reach destination"); 
    } 
    for(Node node = finish; node != null; node = prev.get(node)) { 
     directions.add(node); 
    } 
    directions.reverse(); 
    return directions; 
} 

Answer 2

每次通過你的循環，你叫

directions.Add(current); 

相反，你應該將那一個地方，你真的知道你想要的條目。

Answer 3

對於只有一對的答案而不是所有對的答案都不是一件簡單的事。計算最短路徑的常用方法是像您一樣開始，但是每當遇到新節點時記錄一次，並記錄路徑上的前一個節點。然後，當您到達目標節點時，您可以沿着反向鏈接到源並獲取路徑。因此，從環取出directions.add(current)，並添加代碼類似於下面的

Map<Node,Node> backlinks = new HashMap<Node,Node>(); 

在開始

，然後在循環

if (!backlinks.containsKey(node)) { 
    backlinks.add(node, current); 
    q.add(node); 
} 

，然後在最後，就構建在directions列表向後使用backlinks地圖。

Answer 4

當您將它們放到隊列中時，您必須將父節點包含到每個節點。然後，您可以遞歸讀取該列表中的路徑。

說你想找到在此圖中從A到d的最短路徑：

 /B------C------D 
/    | 
A    /
    \   /
    \E--------- 

每次排隊節點時間，跟蹤你有來這裏的路上。 因此在步驟1 B（A）E（A）放在隊列中。在第二步中，B被取出，C（B）被放入隊列中等等。然後通過「向後」遞歸，很容易再次找回自己的方式。

只要存在節點並保留鏈接，最好的方法可能是創建一個數組（這是通常在ie。Dijkstra中完成的）。

Answer 5

謝謝你Giolekva！

我重寫了它，重構了一些：

• 訪問節點的集合並不一定是一個地圖。
• 對於路徑重構，可以查找下一個節點，而不是之前的節點，從而不需要反轉方向。

public List<Node> getDirections(Node sourceNode, Node destinationNode) { 
    //Initialization. 
    Map<Node, Node> nextNodeMap = new HashMap<Node, Node>(); 
    Node currentNode = sourceNode; 

    //Queue 
    Queue<Node> queue = new LinkedList<Node>(); 
    queue.add(currentNode); 

    /* 
    * The set of visited nodes doesn't have to be a Map, and, since order 
    * is not important, an ordered collection is not needed. HashSet is 
    * fast for add and lookup, if configured properly. 
    */ 
    Set<Node> visitedNodes = new HashSet<Node>(); 
    visitedNodes.add(currentNode); 

    //Search. 
    while (!queue.isEmpty()) { 
     currentNode = queue.remove(); 
     if (currentNode.equals(destinationNode)) { 
      break; 
     } else { 
      for (Node nextNode : getChildNodes(currentNode)) { 
       if (!visitedNodes.contains(nextNode)) { 
        queue.add(nextNode); 
        visitedNodes.add(nextNode); 

        //Look up of next node instead of previous. 
        nextNodeMap.put(currentNode, nextNode); 
       } 
      } 
     } 
    } 

    //If all nodes are explored and the destination node hasn't been found. 
    if (!currentNode.equals(destinationNode)) { 
     throw new RuntimeException("No feasible path."); 
    } 

    //Reconstruct path. No need to reverse. 
    List<Node> directions = new LinkedList<Node>(); 
    for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) { 
     directions.add(node); 
    } 

    return directions; 
}