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

一尘不染

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

algorithm

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

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

阅读 365

2020-07-28

共1个答案

一尘不染

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

私有Map <Node，Boolean >> vis = new HashMap <Node，Boolean>（）;

私有Map <Node，Node> prev = new HashMap <Node，Node>（）;

公开列表getDirections（节点开始，节点完成）{
    列表方向=新的LinkedList（）;
    队列q = new LinkedList（）;
    节点电流=开始；
    q.add（当前）;
    vis.put（current，true）;
    while（！q.isEmpty（））{
        当前= q.remove（）;
        如果（current.equals（finish））{
            打破;
        }其他{
            for（节点节点：current.getOutNodes（））{
                if（！vis.contains（node））{
                    q.add（node）;
                    vis.put（node，true）;
                    prev.put（节点，当前）;
                }
            }
        }
    }
    如果（！current.equals（finish））{
        System.out.println（“无法到达目的地”）;
    }
    for（Node node = finish; node！= null; node = prev.get（node））{
        directions.add（node）;
    }
    directions.reverse（）;
    返回指示；
}

2020-07-28