Algoritmus nejkratší cesty paralelního jednoho zdroje - Parallel single-source shortest path algorithm

Ústřední problém v algoritmu teorie grafů je problém s nejkratší cestou. Jedna z generalizace problému s nejkratší cestou je známá jako single-source-shortest-paths (SSSP) problém, který spočívá v nalezení nejkratší cesty mezi každou dvojicí vrcholů v grafu. Existují klasické sekvenční algoritmy které tento problém řeší, jako např Dijkstrův algoritmus. V tomto článku však uvádíme dva paralelní algoritmy řešení tohoto problému.

Další variantou problému je problém APSP (all-pair-shortest-paths), který má také paralelní přístupy: Paralelní algoritmus nejkratší cesty všech párů.

Definice problému

Nechat ${ displaystyle G = (V, E)}$ být směrovaný graf s ${ displaystyle | V | = n}$ uzly a ${ displaystyle | E | = m}$ hrany. Nechat ${ displaystyle s}$ být rozlišujícím vrcholem (nazývaným "zdroj") a ${ displaystyle c}$ být funkcí přiřazující nezápornou skutečnou váhu každé hraně. Cílem problému s jedním zdrojem a nejkratší cestou je vypočítat pro každý vrchol ${ displaystyle v}$ dosažitelný z ${ displaystyle s}$, váha cesty s minimální hmotností od ${ displaystyle s}$ na ${ displaystyle v}$, označeno ${ displaystyle operatorname {dist} (s, v)}$ a zkráceně ${ displaystyle operatorname {dist} (v)}$. Váha dráhy je součtem hmotností jejích hran. Jsme si stanovili ${ displaystyle operatorname {dist} (u, v): = infty}$ -li ${ displaystyle v}$ je nedosažitelný z ${ displaystyle u}$.^[1]

Algoritmy sekvenční nejkratší cesty běžně používají iterativní metody značení založené na zachování předběžné vzdálenosti pro všechny uzly; ${ displaystyle operatorname {tent} (v)}$ je vždy ${ displaystyle infty}$ nebo váha nějaké cesty z ${ displaystyle s}$ na ${ displaystyle v}$ a tudíž horní hranice ${ displaystyle operatorname {dist} (v)}$. Předběžné vzdálenosti se zlepšují prováděním relaxací okrajů, tj. Hrany ${ displaystyle (v, w) v E}$ sady algoritmů ${ displaystyle operatorname {tent} (w): = min { operatorname {tent} (w), operatorname {tent} (v) + c (v, w) }}$.^[1]

U všech paralelních algoritmů budeme předpokládat a PRAM model se souběžným čtením a souběžným zápisem.

Algoritmus krokování Delta

Krokový algoritmus delta je algoritmus korekce štítků, což znamená, že předběžnou vzdálenost vrcholu lze několikrát korigovat pomocí relaxací hran až do posledního kroku algoritmu, kdy jsou všechny předběžné vzdálenosti pevné.

Algoritmus udržuje způsobilé uzly s předběžnými vzdálenostmi v řadě segmentů, z nichž každý představuje rozsah vzdáleností velikosti ${ displaystyle Delta}$. Během každé fáze algoritmus odstraní všechny uzly prvního neprázdného kbelíku a maximálně uvolní všechny odchozí hrany váhy ${ displaystyle Delta}$. Hrany s vyšší hmotností se uvolní až po jistém vyrovnání příslušných počátečních uzlů.^[1] Parametr ${ displaystyle Delta}$ je kladné reálné číslo, které se také říká „šířka kroku“ nebo „šířka kbelíku“.^[1]

Paralelismus se získá současným odstraněním všech uzlů prvního neprázdného kbelíku a uvolněním jejich odchozích světelných hran v jedné fázi. Pokud uzel ${ displaystyle v}$ byl odstraněn z aktuálního bloku ${ displaystyle B [i]}$ s konečnou hodnotou vzdálenosti pak v nějaké následující fázi ${ displaystyle v}$ bude nakonec znovu vložen do ${ displaystyle B [i]}$ a odchozí světelné hrany ${ displaystyle v}$ bude znovu uvolněná. Zbývající těžké hrany vycházející ze všech uzlů, ze kterých byly odstraněny ${ displaystyle B [i]}$ zatím jsou uvolněné jednou provždy, když ${ displaystyle B [i]}$ nakonec zůstane prázdný. Následně algoritmus vyhledá další neprázdný kbelík a pokračuje, jak je popsáno výše.^[1]

Maximální nejkratší váha cesty pro zdrojový uzel ${ displaystyle s}$ je definován jako ${ displaystyle L (s): = max { operatorname {dist} (s, v): operatorname {dist} (s, v) < infty }}$, zkráceně ${ displaystyle L}$.^[1] Velikost cesty je také definována jako počet hran na cestě.

Rozlišujeme světlé hrany od těžkých hran, kde mají lehké hrany váhu maximálně ${ displaystyle Delta}$ a těžké hrany mají váhu větší než ${ displaystyle Delta}$ .

Následuje krokový algoritmus delta v pseudokódu:

1  pro každého ${ displaystyle v  ve V}$ dělat ${ displaystyle  operatorname {tent} (v): =  infty}$2  ${ displaystyle relax (s, 0)}$; (* Vložte zdrojový uzel se vzdáleností 0 *) 3 zatímco ${ displaystyle  lnot isEmpty (B)}$ dělat                                         (* Fáze: Některé uzly ve frontě zbývají (a) *) 4 | ${ displaystyle i: =  min  {j  geq 0: B [j]  neq  emptyset }}$                                    (* Nejmenší neprázdný kbelík (b) *) 5 | ${ displaystyle R: =  emptyset}$                                                       (* Pro segment B [i] zatím nejsou odstraněny žádné uzly *) 6 | zatímco ${ displaystyle B [i]  neq  emptyset}$ dělat                                             (* Nová fáze (c) *) 7 | | ${ displaystyle Req: = findRequests (B [i], light)}$                            (* Vytvořit požadavky na světlé hrany (d) *) 8 | | ${ displaystyle R: = R  pohár B [i]}$                                               (* Pamatujte si smazané uzly (e) *) 9 | | ${ displaystyle B [i]: =  emptyset}$                                                    (* Aktuální kbelík prázdný *) 10 | | ${ displaystyle relaxRequests (žádost)}$                                         (* Uvolněte se, uzly mohou (znovu) vstoupit do B [i] (f) *) 11 | ${ displaystyle Req: = findRequests (R, heavy)}$                                (* Vytvořit požadavky na těžké hrany (g) *) 12 | ${ displaystyle relaxRequests (žádost)}$                                           (* Relaxace nenaplní B [i] (h) *) 1314 Funkce ${ displaystyle findRequests (V ', druh:  {{ text {light}}, { text {heavy}} })}$: sada požadavku15 vrátit se ${ displaystyle  {(w,  operatorname {tent} (v) + c (v, w)): v  ve V ' zemi (v, w)  v E _ { textu {druhu}} }}$1617 Postup ${ displaystyle relaxRequests (žádost)}$18   pro každého ${ displaystyle (w, x)  v požadavku}$ dělat ${ displaystyle relax (w, x)}$1920 Postup ${ displaystyle relax (w, x)}$                                             (* Vložte nebo přesuňte w do B, pokud x < operatorname {tent} (w) *) 21 -li ${ displaystyle x < operatorname {tent} (w)}$ pak22  | ${ displaystyle B [ lfloor  operatorname {tent} (w) /  Delta  rfloor]: = B [ lfloor  operatorname {tent} (w) /  Delta  rfloor]  setminus  {w }}$                       (* Pokud je v, vyjměte ze starého kbelíku *) 23 | ${ displaystyle B [ lfloor x /  Delta  rfloor]: = B [ lfloor x /  Delta  rfloor]  pohár  {w }}$                                   (* Vložit do nového bloku *) 24 | ${ displaystyle  operatorname {tent} (w): = x}$

Příklad

Příklad grafu

Následuje podrobný popis provedení algoritmu pro malý ukázkový graf. Zdrojovým vrcholem je vrchol A a ${ displaystyle Delta}$ se rovná 3.

Na začátku algoritmu mají všechny vrcholy kromě zdrojového vrcholu A nekonečné předběžné vzdálenosti.

Kbelík ${ displaystyle B [0]}$ má rozsah ${ displaystyle [0,2]}$, Kbelík ${ displaystyle B [1]}$ má rozsah ${ displaystyle [3,5]}$ a kbelík ${ displaystyle B [2]}$ má rozsah ${ displaystyle [6,8]}$.

Kyblík ${ displaystyle B [0]}$ obsahuje vrchol A. Všechny ostatní segmenty jsou prázdné.

Uzel	A	B	C	D	E	F	G
Předběžná vzdálenost	0	${ displaystyle infty}$	${ displaystyle infty}$	${ displaystyle infty}$	${ displaystyle infty}$	${ displaystyle infty}$	${ displaystyle infty}$

Algoritmus uvolňuje všechny dopadající světelné hrany ${ displaystyle B [0]}$, což jsou hrany spojující A s B, G a E.

Vrcholy B, G a E jsou vloženy do kbelíku ${ displaystyle B [1]}$. Od té doby ${ displaystyle B [0]}$ je stále prázdná, těžká hrana spojující A s D je také uvolněná.

Uzel	A	B	C	D	E	F	G
Předběžná vzdálenost	0	3	${ displaystyle infty}$	5	3	${ displaystyle infty}$	3

Nyní dopadají světelné hrany ${ displaystyle B [1]}$ jsou uvolnění. Vrchol C je vložen do kbelíku ${ displaystyle B [2]}$. Od teď ${ displaystyle B [1]}$ je prázdná, těžká hrana spojující E s F může být uvolněná.

V dalším kroku kbelík ${ displaystyle B [2]}$ je zkoumáno, ale nevede k žádným úpravám předběžných vzdáleností.

Algoritmus končí.

Runtime

Jak již bylo zmíněno dříve, ${ displaystyle L}$ je maximální nejkratší váha dráhy.

Pojďme nazvat cestu s maximální hmotností ${ displaystyle Delta}$ a bez opakování hran a ${ displaystyle Delta}$-cesta.

Nechat ${ displaystyle C _ { Delta}}$ označuje množinu všech párů uzlů ${ displaystyle langle u, v rangle}$ připojeno některými ${ displaystyle Delta}$-cesta ${ displaystyle (u, tečky, v)}$ a nechte ${ displaystyle n _ { Delta}: = | C _ { Delta} |}$. Podobně definujte ${ displaystyle C _ { Delta +}}$ jako soubor trojic ${ displaystyle langle u, v ', v rangle}$ takhle ${ displaystyle langle u, v ' rangle v C _ { Delta}}$ a ${ displaystyle (v ', v)}$ je světelná hrana a nechte ${ displaystyle m _ { Delta}: = | C _ { Delta +} |}$.

Algoritmus sekvenčního delta krokování potřebuje nanejvýš${ displaystyle { mathcal {O}} (n + m + n _ { Delta} + m _ { Delta} + L / Delta)}$ operace. Jednoduchá paralelizace běží v čase ${ displaystyle { mathcal {O}} vlevo ({ frac {L} { Delta}} cdot d ell _ { Delta} log n vpravo)}$ .^[1]

Pokud vezmeme ${ displaystyle Delta = Theta (1 / d)}$ pro grafy s maximálním stupněm ${ displaystyle d}$ a náhodné hmotnosti hran rovnoměrně rozložené v ${ displaystyle [0,1]}$, sekvenční verze algoritmu potřebuje ${ displaystyle { mathcal {O}} (n + m + dL)}$ průměrný celkový čas a jednoduchá paralelizace trvá v průměru ${ displaystyle { mathcal {O}} (d ^ {2} L log ^ {2} n)}$.^[1]

Graf 500

Třetí výpočetní jádro Graf 500 benchmark spouští výpočet nejkratší cesty z jednoho zdroje.^[2] Referenční implementace benchmarku Graph 500 používá pro tento výpočet delta krokovací algoritmus.

Algoritmus krokování poloměru

U algoritmu krokování poloměru musíme předpokládat, že náš graf ${ displaystyle G}$ je neorientovaný.

Vstupem do algoritmu je vážený, neorientovaný graf, zdrojový vrchol a hodnota cílového poloměru pro každý vrchol, daná jako funkce ${ displaystyle r: V rightarrow mathbb {R} _ {+}}$.^[3] Algoritmus navštěvuje vrcholy ve vzrůstající vzdálenosti od zdroje ${ displaystyle s}$. Na každém kroku ${ displaystyle i}$, Poloměrný krok zvyšuje poloměr se středem ${ displaystyle s}$ z ${ displaystyle d_ {i-1}}$ na ${ displaystyle d_ {i}}$ a urovná všechny vrcholy ${ displaystyle v}$ v mezikruží ${ displaystyle d_ {i-1}$.^[3]

Následuje algoritmus krokování poloměru v pseudokódu:

    Vstup: Graf ${ displaystyle G = (V, E, w)}$, poloměry vrcholů ${ displaystyle r ( cdot)}$a zdrojový uzel ${ displaystyle s}$.    Výstup: Vzdálenosti grafu ${ displaystyle  delta ( cdot)}$ z ${ displaystyle s}$. 1  ${ displaystyle  delta ( cdot)  leftarrow +  infty}$, ${ displaystyle  delta (y)  leftarrow 0}$ 2  pro každého ${ displaystyle v  v N (s)}$ dělat ${ displaystyle  delta (v)  leftarrow w (s, v)}$, ${ displaystyle S_ {0}  leftarrow  {s }}$, ${ displaystyle i  leftarrow 1}$ 3  zatímco ${ displaystyle | S_ {i-1} | <| V |}$ dělat 4  | ${ displaystyle d_ {i}  leftarrow  min _ {v  in V  setminus S_ {i-1}}  { delta (v) + r (v) }}$ 5  | opakovat    6  | | pro každého ${ displaystyle u  in V  setminus S_ {i-1}}$ Svatý ${ displaystyle  delta (u)  leq d_ {i}}$ dělat 7  | | | pro každého ${ displaystyle v  v N (u)  setminus S_ {i-1}}$ dělat 8  | | | | ${ Displaystyle  delta (v)  leftarrow  min  { delta (v),  delta (u) + w (u, v) }}$ 9  | dokud Ne ${ displaystyle  delta (v)  leq d_ {i}}$ bylo aktualizováno 10 | ${ displaystyle S_ {i} =  {v ; | ; delta (v)  leq d_ {i} }}$ 11 | ${ displaystyle i = i + 1}$ 12 vrátit se ${ displaystyle  delta ( cdot)}$

Pro všechny ${ displaystyle S subseteq V}$, definovat ${ displaystyle N (S) = bigcup _ {u v S} {v v V mid d (u, v) v E }}$ být soused set S. Při provádění standardu vyhledávání na šířku nebo Dijkstrův algoritmus, hranice je sousední množina všech navštívených vrcholů.^[3]

V algoritmu Radius-Stepping je nová kulatá vzdálenost ${ displaystyle d_ {i}}$ se rozhoduje v každém kole s cílem omezit počet dílčích kroků. Algoritmus zabírá poloměr ${ displaystyle r (v)}$ pro každý vrchol a vybere a ${ displaystyle d_ {i}}$ na krok ${ displaystyle i}$ tím, že vezmeme minimum ${ displaystyle delta (v) + r (v)}$ nade vše ${ displaystyle v}$ na hranici (řádek 4).

Řádky 5-9 pak spusťte Bellman-Ford dílčí kroky, dokud všechny vrcholy s poloměrem menším než ${ displaystyle d_ {i}}$ jsou usazeni. Vrcholy uvnitř ${ displaystyle d_ {i}}$ jsou poté přidány do navštívené sady ${ displaystyle S_ {i}}$.^[3]

Příklad

Příklad grafu

Následuje podrobný popis provedení algoritmu pro malý ukázkový graf. Zdrojovým vrcholem je vrchol A a poloměr každého vrcholu se rovná 1.

Na začátku algoritmu mají všechny vrcholy kromě zdrojového vrcholu A nekonečné pokusné vzdálenosti, označené ${ displaystyle delta}$ v pseudokódu.

Všichni sousedé z A jsou uvolnění a ${ displaystyle S_ {0} = {A }}$.

Uzel	A	B	C	D	E	F	G
Předběžná vzdálenost	0	3	${ displaystyle infty}$	5	3	${ displaystyle infty}$	3

Proměnná ${ displaystyle d_ {1}}$ je zvoleno rovné 4 a sousedé vrcholů B, E a G jsou uvolnění. ${ displaystyle S_ {1} = {A, B, E, G }}$

Proměnná ${ displaystyle d_ {2}}$ je zvoleno rovné 6 a žádné hodnoty se nezmění. ${ displaystyle S_ {2} = {A, B, C, D, E, G }}$.

Proměnná ${ displaystyle d_ {3}}$ je vybráno rovné 9 a žádné hodnoty se nezmění. ${ displaystyle S_ {3} = {A, B, C, D, E, F, G }}$.

Algoritmus končí.

Runtime

Po fázi předzpracování může algoritmus krokování poloměru vyřešit problém SSSP v ${ displaystyle { mathcal {O}} (m log n)}$ pracovat a ${ displaystyle { mathcal {O}} ({ frac {n} {p}} log n log pL)}$ hloubka, pro ${ displaystyle p leq { sqrt {n}}}$. Kromě toho trvá fáze předzpracování ${ displaystyle { mathcal {O}} (m log n + np ^ {2})}$ pracovat a ${ displaystyle { mathcal {O}} (p ^ {2})}$ hloubka, nebo ${ displaystyle { mathcal {O}} (m log n + np ^ {2} log n)}$ pracovat a ${ displaystyle { mathcal {O}} (p log p)}$ hloubka.^[3]

Reference