グラフ内の最短経路の数

Question

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

How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

しかし、私はかなりそれを理解していません。他の言葉でアルゴリズムを書き留めておいて、それをよりよく理解できるでしょうか？

Answer 1

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

各頂点xは、countとvalの2つの値を関連付けます。countはsrcからxまでの最短パスの数で、valはsrcからxまでの最短距離です。また、ノードが最初に到着したかどうかを知らせる訪問された変数を維持する。

それはUを介して今までソースから唯一の経路を有するよう

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

ノードが最初に訪問される、通常のBFSアルゴリズムを適用し、V点で最大ので、最短経路は、U点で最大1つの+最短経路であり、数最短経路でvに達する方法はcount [u]と同じですが、uにはソースから到達する5つの方法があるため、これらの5つの方法だけがuを介して最初に遭遇するのでvまで拡張することができるので

vが既に訪問されている場合は、他のいくつかの経路を経由してvまで別の経路がありますertices、次いで3つのケースが発生する：いくつかの他の経路を介してV点で最大DISTである現在のVal [V]はヴァルに等しい

1 :if val[v] == val[u]+1 

場合[U] +1、すなわち我々は電流を用いてVに到達するための同等の最短距離を有しますuを通る経路とvまでの他の経路との間の距離は、vまでの最短距離は変わらないが、経路の数はuに到達する経路の数によって増加する。到達Vの電流経路がヴァルの前の値よりも小さい場合

count[v] = count[v]+count[u] 

2: val[v] > val[u]+1 

[V]、その後、valが[V]の電流経路を保存され、[V]また

val[v] = val[u]+1 
count[v] = count[u] 

第三の更新されたカウント現在のパスのパスが以前のパスよりも大きい場合、この場合、val [v]とcount [v]の値を変更する必要はありません。

このアルゴリズムは、BFSが完了するまで実行してください。 最後のval [dest]にはsourceからの最短距離が含まれ、count [dest]にはsrcからdestまでのウェイ数が含まれます。