重み付け有向グラフで最も重みの小さいパスの重みを求めるアルゴリズム

Question

G =（V、E）有向グラフを与えられ、すべてのエッジの重みが「0」または「1」です。

私はグラフの中で「A」という名前の頂点が与えられています.Vの各vについて、時間の最も小さい重みを持つAからvへの経路の重みを求める必要があります。 ）。 私はBFSまたはDFSのみを使用する必要があります（これはおそらくBFSの問題です）。

私は、それらの間に0の頂点を持つ頂点が結合された上でBFSを実行する新しいグラフを作成しようとしますが、グラフの方向が壊れてしまいます（これは、グラフが無向であるか、 {2,1}、2の辺については新しい頂点を作成します）。

私は助けていただきありがとうございます。

おかげ

Answer 1

DFSとBFSの組み合わせで実現できると思います。

重み付けされていないグラフの元のBFSでは、探索されていないノードの距離が探索されたノードの距離より大きいか等しい距離であることが不変である。

私たちのBFSでは、各ノードに対して、まずすべての0の重み付けされたエッジを通してDFSを行い、距離をマークし、それを探索としてマークします。次に、BFSの他のノードを続けることができます。

Array Seen[] = false 
Empty queue Q 
E' = {(a, b) | (a, b) = 0 and (a, b) is of E} 

DFS(V, E', u) 
    for each v is adjacent to u in E' // (u, v) has an edge weighted 0 
     if Seen[v] = false 
      v.dist = u.dist 
      DFS(V, E', v) 
    Seen[u] = true 
    Enqueue(Q, u) 

BFS(V, E, source) 
    Enqueue(Q, source) 
    source.dist = 0 
    DFS(V, E', source) 
    while (Q is not empty) 
     u = Dequeue(Q) 
     for each v is adjacent to u in E 
      if Seen[v] = false 
       v.dist = u.dist + 1 
       Enqueue(Q, v) 
     Seen[u] = true 

BFSを実行すると、ノードソースから最短の距離が得られます。単一ノードへの最短距離のみを必要とする場合は、宛先ノードが表示されたら終了してください。そして、はい、それはO（V + E）時間の複雑さの要件を満たしています。

Answer 2

この問題は、単一ソース最短パスの問題のように変形することができます。あなたは簡単に初期のグラフに、我々はいくつかの最低限のパスを持っていた場合ならばということを観察することができ、すべてのエッジ方向を逆にする必要があると頂点A.

から各頂点vの最小距離を見つける

頂点vをAに変更すると、エッジ方向を変更した後、Aからvまで同じ最小限のパスを持つことになります。

これは単にDijkstraのどちらかで行うことができます。または、エッジはちょうど2つの値{0と1}また、変更されたBFSによって行われます（最初に、距離0、次に1、次に2などの頂点に移動します）。