未加权图的最短路径(最少节点) [英] Shortest path (fewest nodes) for unweighted graph

问题描述

我正在尝试构建一种方法，该方法返回未加权图中从一个节点到另一个节点的最短路径.我考虑过使用 Dijkstra 的，但这似乎有点矫枉过正，因为我只想要一对.相反，我实施了广度优先搜索，但问题是我的返回列表包含一些我不想要的节点 - 我该如何修改代码以实现我的目标?

公共列表<节点>getDirections(节点开始，节点完成){列表<节点>方向 = new LinkedList();队列<节点>q = new LinkedList();节点电流 = 开始；q.add(当前)；while(!q.isEmpty()){当前 = q.remove();方向.添加(当前)；如果(当前.等于(完成)){休息;}别的{for(节点节点:current.getOutNodes()){如果(！q.contains(节点)){q.add(节点)；}}}}如果(！current.equals(完成)){System.out.println("无法到达目的地");}返回方向；}

解决方案

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

<前>private Map> vis = new HashMap();私有地图<节点，节点>prev = new HashMap();公共列表 getDirections(节点开始，节点完成){列表方向 = new LinkedList();队列 q = new LinkedList();节点电流 = 开始；q.add(当前)；vis.put(current, true);while(!q.isEmpty()){当前 = q.remove();如果(当前.等于(完成)){休息;}别的{for(节点节点:current.getOutNodes()){如果(！vis.contains(节点)){q.add(节点)；vis.put(node, true);prev.put(节点，当前)；}}}}如果(！current.equals(完成)){System.out.println("无法到达目的地");}for(节点节点=完成；节点！=空；节点=prev.get(节点)){方向.添加(节点)；}方向.反向()；返回方向；}

I'm trying build a method which returns the shortest path from one node to another in an unweighted graph. I considered the use of Dijkstra's but this seems a bit overkill since I only want one pair. Instead I have implemented a breadth-first search, but the trouble is that my returning list contains some of the nodes that I don't want - how can I modify my code to achieve my goal?

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

解决方案

Actually your code will not finish in cyclic graphs, consider graph 1 -> 2 -> 1. You must have some array where you can flag which node's you've visited already. And also for each node you can save previous nodes, from which you came. So here is correct code:

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

这篇关于未加权图的最短路径(最少节点)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！