Johnsonův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. listopadu 2019; ověření vyžaduje 1 úpravu .

Johnsonův algoritmus – umožňuje vám najít nejkratší cesty mezi všemi dvojicemi vrcholů ve váženém orientovaném grafu . Tento algoritmus funguje, pokud graf obsahuje hrany s kladnou nebo zápornou váhou, ale neexistují žádné cykly se zápornou váhou. Pojmenován po D. B. Johnson , který publikoval algoritmus v roce 1977.

Algoritmus

Daný graf s váhovou funkcí . Pokud jsou váhy všech hran v grafu nezáporné, můžete najít nejkratší cesty mezi všemi páry vrcholů spuštěním Dijkstrova algoritmu jednou pro každý vrchol. Pokud graf obsahuje hrany se zápornými vahami, ale žádné cykly se zápornými vahami, lze vypočítat novou sadu hran s nezápornými vahami, což umožňuje použít předchozí metodu. Nová sada sestávající ze závaží hran musí splňovat následující vlastnosti. $G=(V,E)$ $\omega \colon E\to R$ $\omega$ ${\hat {\omega ))$

Pro všechny hrany je nová hmotnost . $(u,\;v)$ ${\hat {\omega }}(u,\;v)>0$
Pro všechny páry vrcholů je cesta nejkratší cestou z vrcholu k vrcholu pomocí váhové funkce tehdy a jen tehdy, když je zároveň nejkratší cestou od vrcholu k vrcholu s váhovou funkcí . $u,\;v\in V$ $p$ $u$ $proti$ $\omega$ $p$ $u$ $proti$ ${\hat {\omega ))$

Zachování nejkratších cest

Lemma (Změna vah zachovává nejkratší cesty). Nechť je vážený orientovaný graf s váhovou funkcí a nechť je libovolná funkce, která mapuje vrcholy na reálná čísla. Pro každou hranu definujeme $G=(V,\;E)$ $\omega \colon E\to R$ $h\colon V\to R$ $(u,\;v)\in E$

{\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v).

Dovolit být libovolná cesta od vrcholu k vrcholu . je nejkratší cesta s váhovou funkcí právě tehdy, když je to nejkratší cesta s váhovou funkcí , tj. rovnost je ekvivalentní rovnosti . Kromě toho graf obsahuje cyklus se zápornou váhou pomocí váhové funkce právě tehdy, pokud obsahuje cyklus se zápornou váhou pomocí váhové funkce . $p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle$ $v_{0}$ $v_{k}$ $p$ $\omega$ ${\hat {\omega ))$ $\omega (p)=\delta (v_{0},\;v_{k})$ ${\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})$ $G$ $\omega$ ${\hat {\omega ))$

Změna hmotnosti

Pro tento graf vytvořte nový graf , kde , pro nějaký nový vrchol a . $G'=(V',\;E')$ ${\displaystyle V'=V\cup \{s\))$ $není \in V$ $E'=E\cup \{(s,\;v):v\in V\}$
Rozšiřme váhovou funkci tak, aby rovnost platila pro všechny vrcholy . $\omega$ $v\in V$ $\omega (s,\;v)=0$
Dále definujeme pro všechny vrcholy hodnotu a nové váhy pro všechny hrany . $v\in V'$ $h(v)=\delta (s,\;v)$ ${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0$

Základní postup

Johnsonův algoritmus používá Bellman-Fordův algoritmus a Dijkstrův algoritmus implementované jako podprogramy. Hrany jsou uloženy jako seznamy sousedních vrcholů. Algoritmus vrací běžnou matici velikosti , kde , nebo dává zprávu, že vstupní graf obsahuje cyklus se zápornou váhou. ${\displaystyle D=d_{ij))$ $|V|\times |V|$ $d_{ij}=\delta(i,\;j)$

Johnson's Algorithm Sestavte graf , pokud Bellman_Ford = FALSE , pak vytiskněte "Vstupní graf obsahuje cyklus se zápornou váhou" vraťte ø pro každou hodnotu nastavte na ,

G'

(G',\;\omega ,\;s)

v\in V'

h(v)

\delta (s,\;v)

vypočítané Bellman-Fordovým algoritmem for pro každou hranu proveďte pro pro každý vrchol do Dijkstrův algoritmus vypočítá hodnoty pro všechny vrcholy pro pro každý vrchol do return D

(u,\;v)\in E'

{\hat {\omega }}(u,\;v)\leftarrow \omega (u,\;v)+h(u)-h(v)

u\in V

(G,\;{\hat {\omega )),\;u)

{\hat {\delta }}(u,\;v)

v\in V

v\in V

d_{uv}\leftarrow {\hat {\delta }}(u,\;v)+h(v)-h(u)

Obtížnost

Pokud je fronta s neklesající prioritou v Dijkstrově algoritmu implementována jako Fibonacciho halda , pak je doba běhu Johnsonova algoritmu . S jednodušší implementací fronty s neklesající prioritou se doba běhu rovná , ale u řídkých grafů se tato hodnota v asymptotickém limitu chová lépe než doba běhu Floyd-Warshallova algoritmu . $O(V^{2}\log V+VE)$ $O(VE\log V)$

Viz také

Odkazy

Vizualizér algoritmů

Literatura

Thomas H. Kormen aj. Algoritmy: konstrukce a analýza. - 2. vyd. - M . : Williams Publishing House , 2007. - S. 726. - ISBN 5-8459-0857-4 .
Thomas H. Kormen aj. Algoritmy: konstrukce a analýza. - 1. vyd. - M .: MTSNMO , 2004. - S. 523. - ISBN 5-900916-37-5 .

Algoritmy pro vyhledávání grafů
Neinformované metody	Obousměrné vyhledávání Hledání paprskem Lexikografická šířka první hledání Šířka první hledání Vyhledávání podle nákladového kritéria Hloubka první hledání Zpětné vyhledávání Hledejte podle výstupu na vrchol Hloubkově omezené hledání Hloubkové vyhledávání s iterativním prohlubováním
Informované metody	Výstřižek alfa beta Metoda větvení a vazby Hledejte podle první nejlepší shody A* B* D* Hledání přechodového bodu IDA* Rekurzivní vyhledávání první nejlepší shody SMA*
Zkratky	Vlnový algoritmus Bellman-Fordův algoritmus Dijkstrův algoritmus Johnsonův algoritmus Levitův algoritmus Floyd-Warshall algoritmus Hledání okrajů
Minimální kostra	Borůvkův algoritmus Primův algoritmus Kruskalův algoritmus
jiný	Algoritmus Britského muzea Edmondsův algoritmus Přechod stromu Algoritmus nejbližšího souseda v problému obchodního cestujícího