17

BFS を使用して、グラフの 2 つのノード間のすべてのパスの数を見つける必要があります。私の質問への答えはここにあると思います：

有向グラフと線形時間で、2つの頂点間の異なる最短経路の数を見つける方法は?

しかし、私はそれをよく理解していません。私がそれをよりよく理解できるように、誰かがアルゴリズムを言い換えて書き留めてもらえますか?

4

1 に答える 1

31

src から dest に移動する必要があるとします。

各頂点 x に 2 つの値 count と val を関連付けます。ここで、count は src から x までの最短経路の数であり、val は src から x までの最短距離です。また、ノードを初めて訪問したかどうかを示す訪問済み変数を維持します。

通常の BFS アルゴリズムを適用し、

Initialize u = src
visited[u] = 1, 
val[u] = 0
count[u] = 1
For each child v of u,
    if v is not visited

ノードが最初に訪問されたとき、src から u を介して現在までのパスが 1 つしかないため、v までの最短パスは (1 + u までの最短パス) であり、最短パスを介して v に到達する方法の数は同じです。 as count[u] として u がソースから到達する方法が 5 つあるとすると、v は u を介して初めて遭遇するため、これらの 5 つの方法のみが v まで拡張できます。

val[v] = val[u]+1,    
count[v] = count[u], 
visited[v] = 1
    
if v is visited

v が既に訪問されている場合、つまり、他のいくつかの頂点を経由して v までの他のパスが存在する場合、3 つのケースが発生します。

  1. 場合val[v] == val[u]+1

現在の val[v] (他のパスを介して v までの距離) が val[u]+1 に等しい場合、つまり、u を通る現在のパスと v までの他のパスを使用して v に到達するための最短距離が等しい場合、その場合、v までの最短距離は同じままですが、u に到達するパスの数だけパスの数が増加します。

count[v] = count[v]+count[u]
  1. 場合val[v] > val[u]+1

レベルごとに BFS を使用してノードをトラバースしているため、このケースは発生しません。グラフは重み付けされていないため、最初に val[v] を設定すると、最短パスの長さが val[v] に含まれていることが保証されます。 src から v へ。

  1. 場合val[v] < val[u]+1

この場合、このパスは最短パスとしてカウントされないため、val[v] と count[v] の値を変更する必要はありません。

BFS が完了するまで、このアルゴリズムを実行します。最後に、val[dest] にはソースからの最短距離が含まれ、count[dest] には src から dest までの経路の数が含まれます。

于 2013-03-04T22:37:02.747 に答える