35

重み付けされていない無向グラフの 2 つのノード間の最短経路をすべて見つける手助けが必要です。

BFS を使用して最短パスの 1 つを見つけることができますが、これまでのところ、それらすべてを見つけて出力する方法がわかりません。

私が使用できるアルゴリズム/疑似コードのアイデアはありますか?

4

6 に答える 6

34

注意点として、グラフ内の 2 つのノード間に指数関数的に多くの最短経路が存在する可能性があることに注意してください。このためのアルゴリズムは、指数関数的な時間がかかる可能性があります。

とはいえ、すべてのパスを見つけることができる比較的単純なアルゴリズムがいくつかあります。これが2つです。

BFS + リバース DFS

グラフに対して幅優先検索を実行する場合、開始ノードからの距離で各ノードにタグを付けることができます。開始ノードは距離 0 にあり、その後、新しいノードが初めて発見されるたびに、その距離は 1 にそれを発見したノードの距離を加えたものになります。そのため、まずグラフに対して BFS を実行し、各ノードまでの距離を書き留めます。

これがあれば、次のようにソースから目的地までの最短経路を見つけることができます。開始ノードから距離 d にある目的地から開始します。ここで、宛先ノードに入るエッジを持つすべてのノードを見てください。ソースから目的地までの最短経路は、距離 d-1 のノードから距離 d の目的地までのエッジをたどることによって終わらなければなりません。したがって、宛先ノードから始めて、距離 d-1 で任意のノードまでエッジを横切って後方に歩きます。そこから、距離 0 の開始ノードに戻るまで、距離 d-2 のノード、距離 d-3 のノードなどに移動します。

この手順では、逆の順序で 1 つのパスが返され、最後に反転して全体のパスを取得できます。

次に、終了ノードから開始ノードに戻る深さ優先検索を実行することにより、ソースから宛先までのすべてのパスを見つけることができます。各ポイントで、現在のノードから距離が等しい前のノードまで逆方向に歩くすべての可能な方法を試します。は、現在のノードの距離よりも正確に 1 小さいです。

(個人的には、これが可能なすべてのパスを見つける最も簡単でクリーンな方法だと思いますが、それは私の意見です。)

複数の親を持つ BFS

この次のアルゴリズムは、すべての可能なパスの生成を高速化するための前処理ステップとして使用できる BFS の変更です。BFS が実行されると、「レイヤー」で外側に進み、距離 0、距離 1、距離 2 などのすべてのノードへの単一の最短パスを取得することを思い出してください。BFS の背後にある動機付けのアイデアは、距離 k + 1開始ノードからの距離は、開始ノードから距離 k にあるノードにエッジで接続する必要があります。BFS は、距離 k にあるノードへの長さ k のパスを見つけ、それをあるエッジだけ延長することにより、距離 k + 1 にあるこのノードを検出します。

目標がすべての最短パスを見つけることである場合は、すべてを拡張して BFS を変更できます。単一のエッジを選択するのではなく、距離 k にあるノードへのパスを距離 k + 1 にあるすべてのノードに接続します。これを行うには、次の方法で BFS を変更します。処理キューにエンドポイントを追加してエッジを処理するときはいつでも、そのノードをすぐに完了としてマークしないでください。代わりに、そのノードに到達するためにたどったエッジで注釈が付けられたキューにそのノードを挿入します。これにより、リンクするノードが複数ある場合、同じノードをキューに複数回挿入できる可能性があります。キューからノードを削除すると、それを完了としてマークし、二度とキューに挿入しません。同様に、単一の親ポインタを保存するのではなく、複数の親ポインタを、そのノードにリンクされたノードごとに 1 つずつ保存します。

この変更された BFS を実行すると、すべてのノードが開始ノードになり、出力エッジがないか、開始ノードから k + 1 の距離にあり、各ノードへのポインターを持つ DAG になります。接続されている距離 k。そこから、選択したノードから DAG 内の開始ノードに戻る可能性のあるすべてのパスをリストすることにより、あるノードから開始ノードまでのすべての最短パスを再構築できます。これは再帰的に行うことができます:

  • 開始ノードからそれ自体へのパスは 1 つだけです。つまり、空のパスです。
  • 他のノードの場合、各出力エッジをたどってパスを見つけることができます。次に、これらのパスを再帰的に拡張して、開始ノードに戻るパスを生成します。

この方法で見つかったパスの多くは宛先ノードの方向に移動しないため、この方法では上記の方法よりも多くの時間とスペースが必要になります。ただし、BFS の後に逆方向検索を行うのではなく、BFS を変更するだけで済みます。

お役に立てれば！

于 2013-01-03T19:15:04.050 に答える
5

@templatetypedef は正しいですが、親リンクがノードに追加される前に実行する必要がある距離チェックについて言及するのを忘れていました。これは、各ノードのソースからの距離を維持し、子の距離を 1 ずつ増やすことを意味します。子がすでに訪問されており、距離が小さい場合は、この増分と親の追加をスキップする必要があります。

public void addParent(Node n) {
    // forbidding the parent it its level is equal to ours
    if (n.level == level) {
        return;
    }
    parents.add(n);

    level = n.level + 1;
}

完全な Java 実装は、次のリンクで見つけることができます。

http://ideone.com/UluCBb

于 2015-01-17T14:23:27.453 に答える
2

これを解決しているときに同様の問題が発生しましたhttps://oj.leetcode.com/problems/word-ladder-ii/

私が対処しようとした方法は、最初に BFS を使用して最短距離を見つけることです。最短距離が d であるとしましょう。ここで DFS を適用し、DFS の再帰呼び出しは再帰レベル d を超えないようにします。

ただし、@templatetypedef で言及されているように、これはすべてのパスを調査することになる可能性があります。

于 2014-09-11T02:38:51.280 に答える
1

まず、幅優先探索を使用してすべてのノードの開始距離を見つけます。

（ノードがたくさんある場合は、 A* を使用して、キューの先頭に があるときに停止できますdistance-to-start > distance-to-start(end-node)。これにより、最短パスに属するすべてのノードが得られます）

次に、エンドノードからバックトラックします。ノードが開始距離の短い 2 つ (またはそれ以上) のノードに接続されている場合は常に、2 つ (またはそれ以上) のパスに分岐します。

于 2013-01-03T19:24:08.797 に答える
0

templatetypedef あなたの答えはとても良かったです。その答えに感謝します(!!)が、1つのポイントを逃しました:

次のようなグラフがある場合:

ABCEF
  | | | |
  D------

このパスが必要だと想像してみましょう:

A -> E.

次のように展開します。

A→B→D→C→F→E。

問題は、E の親として F を持つことですが、 

A->B->D->FE
よりも長い

A->B->C->E.
喜んで追加している両親の距離を追跡する必要があります。

于 2013-09-02T16:41:51.420 に答える