对于加权图最短路径（最少节点） [英] Shortest path (fewest nodes) for unweighted graph

问题描述

我试图建立它返回一个非加权图中从一个节点到另一个节点的最短路径的方法。我认为使用Dijkstra的，但是这似乎有点矫枉过正，因为我只想要一对。相反，我实现了一个广度优先搜索，但麻烦的是，我在返回列表中包含了一些，我不希望节点 - ？我该如何修改我的code来实现我的目标。

 公开名单＆LT;节点＆GT; getDirections（节点开始，节点完成）{
    名单＆LT;节点＆GT;方向=新的LinkedList＆LT;节点＆GT;（）;
    队列＆LT;节点＆GT; Q =新的LinkedList＆LT;节点＆GT;（）;
    节点电流=启动;
    q.add（电流）;
    而（！q.isEmpty（））{
        电流= q.remove（）;
        directions.add（电流）;
        如果（current.equals（完成））{
            打破;
        }其他{
            为（节点节点：current.getOutNodes（））{
                如果（！q.contains（节点））{
                    q.add（节点）;
                }
            }
        }
    }
    如果（！current.equals（完成））{
        的System.out.println（无法到达目的地）;
    }
    返回的方向;
}
 

解决方案

其实你code将无法完成在循环图，考虑图表1 - > 2 - > 1。你必须有一些数组，你可以标记哪些节点的你已经访问过。并且还为每个节点可以节省previous节点，从中你来了。因此，这里是正确的code：

私人地图＆LT;节点，布尔＆GT;>可见=新的HashMap＆LT;节点，布尔＆GT;（）;

私人地图＆LT;节点，节点＆GT; preV =新的HashMap＆LT;节点，节点＆GT;（）;

公开名单getDirections（节点开始，节点完成）{
    清单方向=新的LinkedList（）;
    队列Q =新的LinkedList（）;
    节点电流=启动;
    q.add（电流）;
    vis.put（电流，真正的）;
    而（！q.isEmpty（））{
        电流= q.remove（）;
        如果（current.equals（完成））{
            打破;
        }其他{
            为（节点节点：current.getOutNodes（））{
                如果（！vis.contains（节点））{
                    q.add（节点）;
                    vis.put（节点，真正的）;
                    prev.put（节点，电流）;
                }
            }
        }
    }
    如果（！current.equals（完成））{
        的System.out.println（无法到达目的地）;
    }
    对于（节点node =光洁度;！节点= NULL;节点= prev.get（节点））{
        directions.add（节点）;
    }
    directions.reverse（）;
    返回的方向;
}

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屋！