13

我正在尝试构建一种方法,该方法在未加权图中返回从一个节点到另一个节点的最短路径。我考虑过使用 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;
}
4

5 回答 5

22

实际上,您的代码不会在循环图中完成,请考虑图 1 -> 2 -> 1。您必须有一些数组,您可以在其中标记您已经访问过的节点。而且对于每个节点,您都可以保存您来自的先前节点。所以这里是正确的代码:

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

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

public List getDirections(节点开始,节点结束){
    列表方向 = new LinkedList();
    队列 q = new LinkedList();
    节点电流 = 开始;
    q.add(当前);
    vis.put(当前,真);
    而(!q.isEmpty()){
        当前 = q.remove();
        if (current.equals(finish)){
            休息;
        }别的{
            for(节点节点:current.getOutNodes()){
                如果(!vis.contains(节点)){
                    q.add(节点);
                    vis.put(节点,真);
                    prev.put(节点,当前);
                }
            }
        }
    }
    if (!current.equals(finish)){
        System.out.println("无法到达目的地");
    }
    for(节点节点=完成;节点!=空;节点= prev.get(节点)){
        方向。添加(节点);
    }
    方向.reverse();
    返回方向;
}
于 2009-10-16T18:01:46.423 回答
3

谢谢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;
}
于 2010-11-15T14:11:51.017 回答
1

仅仅得到一对的答案实际上并不比所有对的答案更简单。计算最短路径的常用方法是像你一样开始,但每当遇到新节点时记下并记录路径上的前一个节点。然后,当您到达目标节点时,您可以按照反向链接到源并获取路径。因此,directions.add(current)从循环中删除,并添加如下代码

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

在开始,然后在循环中

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

然后最后,只需使用地图directions反向构建列表。backlinks

于 2009-10-16T17:53:07.317 回答
0

每次通过你的循环,你打电话

directions.Add(current);

相反,您应该将其移动到您真正知道您想要该条目的地方。

于 2009-10-16T17:41:17.043 回答
0

当您将它们放入队列时,您必须将父节点包含到每个节点中。然后,您可以递归地从该列表中读取路径。

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

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

每次将节点排入队列时,请跟踪您到达此处的方式。所以在步骤 1 B(A) E(A) 被放入队列。在第二步中,B 出队,C(B) 被放入队列等。然后很容易再次找到返回的路,只需递归“向后”。

最好的方法可能是创建一个数组,只要有节点并将链接保留在那里,(这通常在 Dijkstra 中完成)。

于 2009-10-16T17:53:55.473 回答