13

重み付けされていないグラフで、あるノードから別のノードへの最短経路を返すメソッドを作成しようとしています。ダイクストラ法の使用を検討しましたが、ペアが1つしかないので、これは少しやり過ぎのようです。代わりに幅優先探索を実装しましたが、問題は、返されるリストに不要なノードが含まれていることです。目標を達成するためにコードを変更するにはどうすればよいですか？

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（Node start、Node finish）{
    リストの方向=newLinkedList（）;
    キューq=new LinkedList（）;
    ノード電流=開始;
    q.add（current）;
    vis.put（current、true）;
    while（！q.isEmpty（））{
        current = q.remove（）;
        if（current.equals（finish））{
            壊す;
        }そうしないと{
            for（ノードノード：current.getOutNodes（））{
                if（！vis.contains（node））{
                    q.add（node）;
                    vis.put（node、true）;
                    prev.put（node、current）;
                }
            }
        }
    }
    if（！current.equals（finish））{
        System.out.println（ "宛先に到達できません"）;
    }
    for（Node node = finish; node！= null; node = prev.get（node））{
        direction.add（node）;
    }
    direction.reverse（）;
    戻り方向;
}
于 2009-10-16T18:01:46.423 に答える
3

ありがとうジョレクバ！

私はそれを書き直し、いくつかをリファクタリングしました：

  • 訪問したノードのコレクションは、マップである必要はありません。
  • パスの再構築では、前のノードの代わりに次のノードを検索できるため、方向を逆にする必要がありません。
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

すべてのペアよりも、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）がキューに入れられます。ステップ2では、Bがデキューされ、C（B）がキューに入れられます。その後、「逆方向」に繰り返すだけで、再び戻る方法を簡単に見つけることができます。

最善の方法は、ノードが存在する限り配列を作成し、そこにリンクを保持することです（これは、通常、ダイクストラ法で行われることです）。

于 2009-10-16T17:53:55.473 に答える