28

演習は次のとおりです。

vとwを有向グラフG=（V、E）の2つの頂点とします。線形時間アルゴリズムを設計して、vとwの間の異なる最短経路（必ずしも頂点が互いに素である必要はない）の数を見つけます。注：Gのエッジは重み付けされていません

この物品税について、私は次のように要約します。

  1. 有向グラフです
  2. 異なる最短経路の数を要求します。まず、パスを最短にする必要があります。次に、長さが同じであるそのような最短パスが複数存在する場合があります。
  3. vとwの間なので、vからwとwからvの両方をカウントする必要があります。
  4. 線形時間。
  5. グラフは重み付けされていません。

上記の点から、私は次のように考えています。

  1. グラフは重み付けされておらず、単一のパスだけでなく、すべての最短パスを見つけようとしているため、ダイクストラのアルゴリズムを使用する必要はありません。
  2. count最短経路の数を維持します
  3. global level最初にvからBFSを使用し、情報も維持したい
  4. global level毎回1ずつ増やしてから、BFSが新しいレベルに到達します
  5. shortest levelwへの最短経路の情報も保持しています
  6. 旅行中に初めてwに会うときは、とにglobal level割り当てshortest levelますcount++。
  7. global levelに等しい限り、wに再び会うたびshortest levelに増加します。count
  8. global levelが大きくなった場合は、shortest level経路ではなく最短経路を探しているので、移動を終了します。
  9. それから私はwからvのためにもう一度2-8をします

私のアルゴリズムは正しいですか？vからw、次にwからvを実行した場合でも、それは線形時間と見なされますか？

4

8 に答える 8

24

これについていくつかのアイデアがあります。

  • v->w からノード x を通る複数の最短パスのみが存在できます。これは、同じ頂点を通る x への複数のパスがある場合、または x が同じ DFS レベルで複数回検出された場合のいずれかです。

証明:x同じ頂点を通って入る複数のパスがある場合、明らかに複数のパスが存在しますx。これは簡単です。ここで、 (最大で)x入る各頂点を通過する方法が 1 つしかないと仮定しましょう。x

x が以前に検出された場合、現在のパスはいずれも別の最短パスに寄与できません。x は以前に遭遇したため、たどることができるすべてのパスは、以前の最短パスよりも少なくとも 1 つ長くなります。したがって、これらのパスはどれも合計に寄与できません。

ただし、これは、各ノードに最大 1 回遭遇するだけで完了することを意味します。したがって、通常の BFS で問題ありません。

  • レベルを知る必要さえありません。代わりに、最終ノードに遭遇すると最終番号を取得できます。

これは、主に単なる BFS である非常に単純なアルゴリズムにコンパイルできます。

 - Mark nodes as visited as usual with BFS.
 - Instead of adding just nodes to the queue in the DFS add nodes plus number of incoming paths.
 - If a node that has been visited should be added ignore it.
 - If you find a node again, which is currently in the queue, do not add it again, instead add the counts together.
 - Propagate the counts on the queue when adding new nodes.
 - when you encounter the final, the number that is stored with it, is the number of possible paths.
于 2012-04-19T13:51:11.093 に答える
10

あなたのアルゴリズムは次のようなグラフで壊れます

  *   *   *   1
 / \ / \ / \ / \
v   *   *   *   w
 \ / \ / \ / \ /
  *   *   *   2

すべてのエッジを左から右に向けます。11 つは を通り、もう1 つは を通ります2が、両方とも1から8 つの異なる最短パスで2到達できるvため、合計 16 のパスがカウントされます。

于 2012-04-19T12:13:56.437 に答える
4

qrqrq が示すように、アルゴリズムは一部のグラフで失敗しますが、BFS の考え方は優れています。代わりに、ゼロに初期化するzサイズの配列を維持してください。より短い距離で|V|発見された頂点への最短経路の数を維持します。また、 から頂点までの距離が 未満の場合、そのようなサイズの配列を維持します。0、0、および1 に初期化し( 長さ 0 からto までのパスが 1 つある)、 toおよびtoの他のすべてのエントリを設定します。ilevelz[i]d|V|d[i]vilevelleveld[v]z[v]vvd-1z0

BFS でからiへのエッジに遭遇するたびに、次のようになります。j

  • の場合d[j] = -1、 および を設定d[j] := levelしz[j] := z[i]ます。
  • の場合d[j] = level、設定しz[j] := z[j] + z[i]ます。
  • それ以外の場合は、何もしません。

その理由は、 から へのすべての最短パスに対して、 からvへiの最短パスが 1 つ存在vするためjです。vこれにより、線形時間内の各頂点への最短パスの数が得られます。同じことをもう一度行いますが、 から始めwます。

于 2012-04-19T13:05:36.183 に答える
2

このアルゴリズムは私には正しいように見えます。

ご存じのように、BFS は線形時間 ( O(N)) 検索Tです。これは、完了するのに必要な時間が最悪でも であるからですT = C + a * N。ここNで、 はノードの数C、aは任意の固定定数です。

あなたの場合、最初に from vto w、次に from wto v- を 2 回実行すると、 (最悪の場合) 2T、 orであり、 newとnew を定義すると、2C + 2a * N線形時間要件も満たされます。 .O(N)C' = 2Ca' = 2aC'a'

于 2012-04-19T11:09:04.497 に答える
0

こうすればいいのか

  1. 目的の頂点に到達してレベルを維持するまで、BFS を使用してトラバースします。
  2. 目的のレベルに到達したら、次のようにレベル テーブルを使用します。

レベル テーブルから、パス内の頂点までの親の数を逆算してトラバースし始めます (最初は目的の頂点になります)。
すべてのステップで、その特定のレベルで見つかった個別の親の数を、目的の頂点までの最短パスに乗算します。レベル 0 に到達するまで
、パスに該当するノードのみを考慮してレベルを上げ、各レベルで見つかった個別の親の数を掛けます。

これは機能しますか？

于 2014-09-17T17:55:10.663 に答える
0

ここにある適切な説明を確認してください：

https://www.geeksforgeeks.org/number-shortest-paths-unweighted-directed-graph/

簡単に言うと、任意の最短経路アルゴリズムを変更できます。更新ステップが来ると、現在の経路提案がその時点までに見つかった最短経路と同じ長さである場合、以前に発見された最短経路の数のカウンターが増加します。

特定のケースで、重み付けされていないか、すべてのエッジの重みが一定のグラフである場合、最も簡単な方法は BFS を変更することです。

于 2018-10-13T20:55:18.867 に答える