並列単一ソース最短経路アルゴリズム

アルゴリズムグラフ理論の中心的な問題は、最短経路問題です。最短経路問題の一般化の 1 つは、単一ソース最短経路 (SSSP)問題として知られており、グラフ内のソース頂点から他のすべての頂点までの最短経路を見つけることで構成されます。この問題を解決する古典的な順次アルゴリズムには、ダイクストラのアルゴリズムなどがあります。ただし、この記事では、この問題を解決する 2 つの並列アルゴリズムを紹介します。 ${\displaystyle s}$

この問題の別のバリエーションは、全ペア最短経路 (APSP) 問題であり、これにも並列アプローチがあります:並列全ペア最短経路アルゴリズム。

をノードと辺を持つ有向グラフとする。を区別された頂点（「ソース」と呼ばれる）とし、 を各辺に非負の実数値の重みを割り当てる関数とする。単一ソース最短経路問題の目的は、から到達可能なすべての頂点について、 からへの最小重み経路の重みを計算することである。は で表され、 と略される。経路の重みはその辺の重みの合計である。から に到達できない場合はとする。^[1]${\displaystyle G=(V,E)}$${\displaystyle |V|=n}$${\displaystyle |E|=m}$${\displaystyle s}$${\displaystyle c}$${\displaystyle v}$${\displaystyle s}$${\displaystyle s}$${\displaystyle v}$${\displaystyle \operatorname {dist} (s,v)}$${\displaystyle \operatorname {dist} (v)}$${\displaystyle \operatorname {dist} (u,v):=\infty }$${\displaystyle v}$${\displaystyle u}$

順次最短経路アルゴリズムでは、一般的に、すべてのノードに対して暫定距離を維持する反復ラベリング法が適用されます。は常にまたはからへの何らかの経路の重みであり、したがって の上限です。暫定距離は、エッジ緩和を実行することによって改善されます。つまり、エッジに対して アルゴリズムは を設定します。^[1]${\displaystyle \operatorname {テント} (v)}$${\displaystyle \infty}$${\displaystyle s}$${\displaystyle v}$${\displaystyle \operatorname {dist} (v)}$${\displaystyle (v,w)\in E}$${\displaystyle \オペレーター名 {テント} (w):=\min\{\オペレーター名 {テント} (w),\オペレーター名 {テント} (v)+c(v,w)\}}$

すべての並列アルゴリズムでは、同時読み取りと同時書き込みを備えたPRAMモデルを想定します。

デルタ ステッピング アルゴリズムはラベル修正アルゴリズムです。つまり、頂点の暫定距離は、アルゴリズムの最後のステップですべての暫定距離が固定されるまで、エッジ緩和によって複数回修正できます。

アルゴリズムは、それぞれがサイズ の距離範囲を表すバケットの配列に、仮の距離を持つ適格なノードを維持します。各フェーズで、アルゴリズムは最初の空でないバケットのすべてのノードを削除し、最大 の重みのすべての出力エッジを緩和します。より高い重みのエッジは、それぞれの開始ノードが確実に解決された後にのみ緩和されます。^[1]パラメータ は正の実数で、「ステップ幅」または「バケット幅」とも呼ばれます。^[1]${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta }$

並列性は、最初の空でないバケットのすべてのノードを同時に削除し、それらの軽いエッジを単一のフェーズで緩和することによって得られます。最終距離値以外の現在のバケットからノードが削除された場合、その後のフェーズで、は最終的に に再挿入され、 の 軽いエッジは再度緩和されます。これまでに から削除されたすべてのノードから発せられる残りの重いエッジは、 finally が空のままである場合に一度だけ緩和されます。その後、アルゴリズムは次の空でないバケットを検索し、上記のように処理を進めます。^[1]${\displaystyle v}$${\displaystyle B[i]}$${\displaystyle v}$${\displaystyle B[i]}$${\displaystyle v}$${\displaystyle B[i]}$${\displaystyle B[i]}$

ソースノードの最大最短経路重みは と定義され、略して と表されます。^[1]また、経路のサイズは、経路上のエッジの数として定義されます。 ${\displaystyle s}$${\displaystyle L(s):=\max\{\operatorname {dist} (s,v):\operatorname {dist} (s,v)<\infty \}}$${\displaystyle L}$

軽いエッジと重いエッジを区別します。軽いエッジの重みは最大で で 、重いエッジの重みは より大きいです。 ${\displaystyle \Delta }$${\displaystyle \Delta }$

以下は擬似コードでのデルタ ステップ アルゴリズムです。

1   foreach  do 
2   ; (*距離0のソースノードを挿入*)${\displaystyle v\in V}$  ${\displaystyle \operatorname {テント} (v):=\infty }$${\displaystyle リラックス(s,0)}$
3   while  do                            (*A フェーズ: キューに入っているノードの一部が残ります (a)*)${\displaystyle \lnot isEmpty(B)}$ 
4                             (*最小の空でないバケツ (b)*)${\displaystyle i:=\min\{j\geq 0:B[j]\neq \emptyset \}}$
5                                                       (*バケットB[i]のノードはまだ削除されていません*)${\displaystyle R:=\emptyset }$
6       while  do                      (*新しいフェーズ (c)*)${\displaystyle B[i]\neq \emptyset }$ 
7                                      (*ライトエッジのリクエストを作成(d)*)${\displaystyle Req:=findRequests(B[i],light)}$
8                                                      （*削除されたノードを記憶する（e）*）${\displaystyle R:=R\cup B[i]}$
9                                                    (*現在のバケットは空です*)${\displaystyle B[i]:=\emptyset }$
10                                                (*緩和を行うと、ノードはB[i] (f)に(再)入る可能性がある*)${\displaystyle リラックスリクエスト(Req)}$
11                                        (*ヘビーエッジのリクエストを作成(g)*)${\displaystyle Req:=findRequests(R,heavy)}$
12                                                （*リラクゼーションではB[i]（h）は補充されません*）${\displaystyle リラックスリクエスト(Req)}$
13
14関数 :リクエストのセット${\displaystyle findRequests(V',kind:\{{\text{light}},{\text{heavy}}\})}$
15     戻る ${\displaystyle \{(w,\operatorname {tent} (v)+c(v,w)):v\in V'\land (v,w)\in E_{\text{kind}}\}}$
16
17手順 
18      foreach do${\displaystyle リラックスリクエスト(Req)}$ ${\displaystyle (w,x)\in Req}$  ${\displaystyle リラックス(w,x)}$
19
20手順                                              ( *B の場合は w を挿入または移動する)${\displaystyle リラックス(w,x)}$${\displaystyle x<\operatorname {tent} (w)}$
21      if  then 
22                                (*もし入っているなら、古いバケットから削除*)${\displaystyle x<\operatorname {tent} (w)}$ ${\displaystyle B[\lfloor \operatorname {tent} (w)/\Delta \rfloor ]:=B[\lfloor \operatorname {tent} (w)/\Delta \rfloor ]\setminus \{w\}}$
23                                           （*新しいバケットに挿入*）${\displaystyle B[\lfloor x/\Delta \rfloor ]:=B[\lfloor x/\Delta \rfloor ]\cup \{w\}}$
24         ${\displaystyle \operatorname {tent} (w):=x}$

以下は、小さなサンプル グラフのアルゴリズム実行のステップごとの説明です。ソース頂点は頂点 A で、3 に等しくなります。 ${\displaystyle \Delta }$

アルゴリズムの開始時には、ソース頂点 A を除くすべての頂点の暫定距離は無限大です。

バケットには範囲があり、バケットには範囲があり、バケットには範囲があります。 ${\displaystyle B[0]}$${\displaystyle [0,2]}$${\displaystyle B[1]}$${\displaystyle [3,5]}$${\displaystyle B[2]}$${\displaystyle [6,8]}$

バケットには頂点 A が含まれます。他のすべてのバケットは空です。 ${\displaystyle B[0]}$

このアルゴリズムは、A を B、G、E に接続するエッジである、 に入射するすべてのライト エッジを緩和します。${\displaystyle B[0]}$

頂点 B、G、E がバケット に挿入されます。はまだ空なので、 A と D を接続する重いエッジも緩和されます。 ${\displaystyle B[1]}$${\displaystyle B[0]}$

これで、 に入射する軽いエッジが緩和されます。頂点 C はバケット に挿入されます。現在は空なので、 E と F を接続する重いエッジを緩和できます。 ${\displaystyle B[1]}$${\displaystyle B[2]}$${\displaystyle B[1]}$

次のステップでは、バケットが検査されますが、暫定的な距離は変更されません。 ${\displaystyle B[2]}$

アルゴリズムは終了します。

前述のように、最大​​最短経路の重みです。 ${\displaystyle L}$

総重量が最大で、エッジの繰り返しがないパスを -パスと呼びます。 ${\displaystyle \Delta }$${\displaystyle \Delta }$

何らかの-パスによって接続されたすべてのノードペアの集合をと します。同様に、 を、およびがライトエッジである3つの要素の集合として定義し、 とします。 ${\displaystyle C_{\Delta }}$${\displaystyle \langle u,v\rangle }$${\displaystyle \Delta }$${\displaystyle (u,\dots ,v)}$${\displaystyle n_{\Delta }:=|C_{\Delta }|}$${\displaystyle C_{\Delta +}}$${\displaystyle \langle u,v',v\rangle }$${\displaystyle \langle u,v'\rangle \in C_{\Delta }}$${\displaystyle (v',v)}$${\displaystyle m_{\Delta }:=|C_{\Delta +}|}$

シーケンシャルデルタステップアルゴリズムは、最大で 回の操作を必要とする。単純な並列化は、時間で実行される。^[1]${\displaystyle {\mathcal {O}}(n+m+n_{\Delta }+m_{\Delta }+L/\Delta )}$${\displaystyle {\mathcal {O}}\left({\frac {L}{\Delta }}\cdot d\ell _{\Delta }\log n\right)}$

最大次数とに一様分布するランダムな辺の重みを持つグラフをとすると、アルゴリズムの逐次バージョンでは合計平均ケース時間が必要となり、単純な並列化では平均 かかります。^[1]${\displaystyle \Delta =\Theta (1/d)}$${\displaystyle d}$${\displaystyle [0,1]}$${\displaystyle {\mathcal {O}}(n+m+dL)}$${\displaystyle {\mathcal {O}}(d^{2}L\log ^{2}n)}$

Graph 500ベンチマークの3番目の計算カーネルは、単一ソースの最短経路計算を実行します。^[2] Graph 500ベンチマークのリファレンス実装では、この計算にデルタステッピングアルゴリズムを使用します。

半径ステップアルゴリズムでは、グラフが無向であると仮定する必要があります。 ${\displaystyle G}$

アルゴリズムへの入力は、重み付けされた無向グラフ、ソース頂点、および関数 として与えられた各頂点のターゲット半径値です。^[3]アルゴリズムは、ソース からの距離が増加する頂点を訪問します。各ステップ で、半径ステップは を中心とする半径を から まで増加させ、すべての頂点を環状 内に配置します。^[3]${\displaystyle r:V\rightarrow \mathbb {R} _{+}}$${\displaystyle s}$${\displaystyle i}$${\displaystyle s}$${\displaystyle d_{i-1}}$${\displaystyle d_{i}}$${\displaystyle v}$${\displaystyle d_{i-1}<d(s,v)\leq d_{i}}$

以下は疑似コードでの半径ステップアルゴリズムです。

    入力: グラフ、頂点の半径、ソース ノード。
    出力:からのグラフの距離。${\displaystyle G=(V,E,w)}$${\displaystyle r(\cdot )}$${\displaystyle s}$${\displaystyle \delta (\cdot )}$${\displaystyle s}$
 1   , 
 2   foreach do , , 
 3   while do 
 4       
 5       repeat    
 6           foreach st do 
 7               foreach do 
 8                   
 9       until noが更新されました${\displaystyle \delta (\cdot )\leftarrow +\infty }$${\displaystyle \delta (s)\leftarrow 0}$ ${\displaystyle v\in N(s)}$  ${\displaystyle \delta (v)\leftarrow w(s,v)}$${\displaystyle S_{0}\leftarrow \{s\}}$${\displaystyle i\leftarrow 1}$ ${\displaystyle |S_{i-1}|<|V|}$ ${\displaystyle d_{i}\leftarrow \min _{v\in V\setminus S_{i-1}}\{\delta (v)+r(v)\}}$ ${\displaystyle u\in V\setminus S_{i-1}}$${\displaystyle \delta (u)\leq d_{i}}$  ${\displaystyle v\in N(u)\setminus S_{i-1}}$ ${\displaystyle \delta (v)\leftarrow \min\{\delta (v),\delta (u)+w(u,v)\}}$${\displaystyle \delta (v)\leq d_{i}}$
 10      
 11      
 12戻る${\displaystyle S_{i}=\{v\;|\;\delta (v)\leq d_{i}\}}$${\displaystyle i=i+1}$ ${\displaystyle \delta (\cdot )}$

すべての に対して、を S の近傍集合と定義します。標準的な幅優先探索またはダイクストラのアルゴリズムの実行中、フロンティアは訪問したすべての頂点の近傍集合です。^[3]${\displaystyle S\subseteq V}$${\displaystyle N(S)=\bigcup _{u\in S}\{v\in V\mid d(u,v)\in E\}}$

半径ステップ アルゴリズムでは、サブステップの数を制限することを目的として、各ラウンドで新しいラウンド距離が決定されます。アルゴリズムは各頂点の半径を取得し、フロンティア全体で最小値を取得して1 つのステップを選択します(行 4)。 ${\displaystyle d_{i}}$${\displaystyle r(v)}$${\displaystyle d_{i}}$${\displaystyle i}$${\displaystyle \delta (v)+r(v)}$${\displaystyle v}$

5行目から9行目では、半径が 未満の頂点がすべて確定するまでベルマンフォードサブステップを実行します。その後、 内の頂点が訪問済みセットに追加されます。^[3]${\displaystyle d_{i}}$${\displaystyle d_{i}}$${\displaystyle S_{i}}$

以下は、小さなグラフの例に対するアルゴリズム実行のステップごとの説明です。ソース頂点は頂点 A であり、各頂点の半径は 1 です。

アルゴリズムの開始時には、ソース頂点 A を除くすべての頂点は、疑似コードで で示される無限の暫定距離を持ちます。 ${\displaystyle \delta }$

A のすべての隣接ノードはリラックスしており、 です。 ${\displaystyle S_{0}=\{A\}}$

変数は4 に等しくなるように選択され、頂点 B、E、G の隣接頂点は緩和されます。${\displaystyle d_{1}}$${\displaystyle S_{1}=\{A,B,E,G\}}$

変数は 6 に等しくなるように選択され、値は変更されません。 ${\displaystyle d_{2}}$${\displaystyle S_{2}=\{A,B,C,D,E,G\}}$

変数は 9 に等しくなるように選択され、値は変更されません。 ${\displaystyle d_{3}}$${\displaystyle S_{3}=\{A,B,C,D,E,F,G\}}$

アルゴリズムは終了します。

前処理段階の後、半径ステップアルゴリズムは仕事と 深さにおけるSSSP問題を解くことができます。さらに、前処理段階では 仕事と 深さ、または仕事と 深さが必要になります。^[3]${\displaystyle {\mathcal {O}}(m\log n)}$${\displaystyle {\mathcal {O}}({\frac {n}{p}}\log n\log pL)}$${\displaystyle p\leq {\sqrt {n}}}$${\displaystyle {\mathcal {O}}(m\log n+np^{2})}$${\displaystyle {\mathcal {O}}(p^{2})}$${\displaystyle {\mathcal {O}}(m\log n+np^{2}\log n)}$${\displaystyle {\mathcal {O}}(p\log p)}$