未加权图的最短路径（最少节点）

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; 
}