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

Question

我正在尝试构建一种方法，该方法将最短路径从一个节点返回一个未加权图的方法。我考虑过使用Dijkstra的，但这似乎有点过分杀伤，因为我只想要一对。取而代之的是，我已经实施了广度优先的搜索，但是问题是我的返回列表包含一些我不想要的节点 - 如何修改代码以实现目标？

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

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

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

每次通过循环，您都会打电话

directions.Add(current);

取而代之的是，您应该将其移至真正知道想要该条目的地方。

Answer 5

将每个节点放在队列中时，必须将父节点包含在每个节点上。然后，您可以递归阅读该列表的路径。

假设您想在此图中找到从A到D的最短路径：

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

每次加入节点时，都会跟踪您到达这里的方式。因此，在步骤1 B（a）e（a）被放在队列上。在第2步中，B被脱水，C（b）放在队列等。然后，只需递归“向后”就可以轻松地再次找到您的路。

最好的方法可能是只要有节点并将链接保留在那里（即通常在dijkstra的工作中）。