未加权图的最短路径(最少节点)

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