Floyd-Warshall 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é 16. dubna 2020; kontroly vyžadují 13 úprav .

Floyd-Warshall algoritmus

Pojmenoval podle	Robert Floyd a Stephen Warshall
Autor	Bernard Roy [d]
účel	hledat v grafu nejkratší cesty mezi libovolným párem vrcholů
Datová struktura	graf
nejhorší čas	$\Theta (\|V\|^{3})$
Nejlepší čas	$\Theta (\|V\|^{3})$
Průměrný čas	$\Theta (\|V\|^{3})$
Náklady na paměť	$\Theta (\|V\|^{2})$
Mediální soubory na Wikimedia Commons

V informatice je Floyd-Warshallův algoritmus (také známý jako Floydův algoritmus , Roy-Warshallův algoritmus , Roy-Floydův algoritmus nebo WFI algoritmus ) algoritmem pro hledání nejkratších cest ve váženém grafu (ale s kladnou nebo zápornou váhou hran) . žádné negativní cykly). V jednom provedení algoritmu budou nalezeny délky (celkové váhy) nejkratších cest mezi všemi dvojicemi vrcholů. Přestože nevrací podrobnosti o samotných cestách, je možné cesty rekonstruovat jednoduchými úpravami algoritmu. K nalezení tranzitivního uzavření vztahu lze také použít varianty algoritmu $R$ nebo (ve spojení se Schulzeho hlasovacím systémem ) nejširší cesty mezi všemi dvojicemi vrcholů ve váženém grafu.

Historie a pojmenování

Algoritmus Floyd-Warshall je příkladem dynamického programování a byl publikován ve své nyní akceptované podobě Robertem Floydem v roce 1962. Je však v podstatě stejný jako algoritmy dříve publikované Bernardem Royem v roce 1959 a také Stephenem Warshallem v roce 1962 pro nalezení tranzitivního uzavření grafu a úzce souvisí s Kleeneovým algoritmem (publikovaným v roce 1956) pro převod deterministického konečného automat na regulární výraz . Moderní formulaci algoritmu ve formě tří vnořených smyček for poprvé popsal Peter Ingerman také v roce 1962.

Algoritmus

Uvažujme graf s vrcholy očíslovanými od 1 do . Algoritmus Floyd-Warshall porovnává všechny možné cesty grafem mezi každou dvojicí vrcholů. Může to udělat pro srovnání v grafu, i když graf může mít až hran a každá kombinace hran je kontrolována. Toho je dosaženo postupným zlepšováním odhadu nejkratší cesty mezi dvěma vrcholy, dokud není odhad optimální. $G$ $PROTI$ $N$ $\Theta (|V|^{3})$ $\Omega (|V|^{2})$

Dále zvažte funkci , která vrací nejkratší možnou cestu z do pomocí pouze vrcholů z množiny jako mezilehlých bodů podél této cesty. Nyní, vzhledem k této funkci, je naším cílem najít nejkratší cestu z každého do každého pomocí libovolného vrcholu v . $\mathrm {shortestPath} (i,j,k)$ $i$ $j$ ${\displaystyle \{1,2,\ldots ,k\))$ $i$ $j$ $\{1,2,\ldots ,N\}$

Pro každou z těchto dvojic vrcholů může být buď $\mathrm {shortestPath} (i,j,k)$

(1) cesta, která neprochází (používá pouze vrcholy z množiny ),

k

\{1,\ldots ,k-1\}

nebo

(2) cesta, která prochází (od do a poté z do , v obou případech se používají pouze mezilehlé vrcholy v ).

k

i

k

k

j

\{1,\ldots ,k-1\}

Víme, že nejlepší cesta z do , což je cesta, která používá pouze vrcholy c do , je definována jako , a je jasné, že pokud by existovala lepší cesta z do do , pak by délka této cesty byla řetězcem tvořeným nejkratší cesty z do (pouze pomocí mezilehlých vrcholů v ) a nejkratší cesty z do (pouze pomocí mezilehlých vrcholů v ). $i$ $j$ $jeden$ $k-1$ $\mathrm {shortestPath} (i,j,k-1)$ $i$ $k$ $j$ $i$ $k$ $\{1,\ldots ,k-1\}$ $k$ $j$ $\{1,\ldots ,k-1\}$

Jestliže je váha hrany mezi vrcholy a , můžeme ji definovat pomocí následujícího rekurzivního vzorce: $w(i,j)$ $i$ $j$ $\mathrm {shortestPath} (i,j,k)$

základní případ

\mathrm {shortestPath} (i,j,0)=w(i,j)

a rekurzivní případ

\mathrm {shortestPath} (i,j,k)=

\mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),

{\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )))

Tento vzorec tvoří základ Floyd-Warshallova algoritmu. Algoritmus funguje tak, že nejprve počítá pro všechny páry pro , a pak , a tak dále. Tento proces pokračuje, dokud není nalezena nejkratší cesta pro všechny páry pomocí jakýchkoli mezilehlých vrcholů. Pseudokód pro tuto základní verzi je následující: $\mathrm {shortestPath} (i,j,k)$ $(i,j)$ $k=1$ $k=2$ $k=N$ $(i,j)$

nechť je dist |V| × |V| pole minimálních vzdáleností inicializovaných jako ∞ (nekonečno) pro každou hranu ( u , v ) do dist[ u ][ v ] ← w( u , v ) // Váha hrany ( u , v ) pro každý vrchol v do dist[ v ][ v ] ← 0 pro k od 1 do |V| pro i od 1 do |V| pro j od 1 do |V| if dist[ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ] dist[ i ][ j ] ← dist[ i ][ k ] + dist[ k ][ j ] konec if

Příklad

Výše uvedený algoritmus je proveden na grafu vlevo dole:

Až do první rekurze vnější smyčky, označované výše k = 0, jediné známé cesty odpovídají jednotlivým hranám v grafu. Pro k = 1 jsou nalezeny cesty, které procházejí vrcholem 1: konkrétně je nalezena cesta [2,1,3], která nahradí cestu [2,3], která má méně hran, ale je delší (z hlediska hmotnosti ). Pro k = 2 jsou nalezeny cesty, které procházejí vrcholy 1,2. Červené a modré rámečky ukazují, jak je cesta [4,2,1,3] sestavena ze dvou známých cest [4,2] a [2,1,3], se kterými jsme se setkali v předchozích iteracích, se 2 na průsečíku. Cesta [4,2,3] se nebere v úvahu, protože [2,1,3] je nejkratší cesta, se kterou jsme se dosud setkali od 2 do 3. Pro k = 3 jsou nalezeny cesty procházející vrcholy 1,2,3. Nakonec pro k = 4 jsou nalezeny všechny nejkratší cesty.

Matice vzdáleností v každé iteraci k, aktualizované vzdálenosti tučně , bude:

k = 0		jeden	2	3	čtyři
k = 0		j
i	jeden	0	∞	−2	∞
	2	čtyři	0	3	∞
	3	∞	∞	0	2
	čtyři	∞	−1	∞	0

k = 1		jeden	2	3	čtyři
k = 1		j
i	jeden	0	∞	−2	∞
	2	čtyři	0	2	∞
	3	∞	∞	0	2
	čtyři	∞	−1	∞	0

k = 2		jeden	2	3	čtyři
k = 2		j
i	jeden	0	∞	−2	∞
	2	čtyři	0	2	∞
	3	∞	∞	0	2
	čtyři	3	−1	jeden	0

k = 3		jeden	2	3	čtyři
k = 3		j
i	jeden	0	∞	−2	0
	2	čtyři	0	2	čtyři
	3	∞	∞	0	2
	čtyři	3	−1	jeden	0

k = 4		jeden	2	3	čtyři
k = 4		j
i	jeden	0	−1	−2	0
	2	čtyři	0	2	čtyři
	3	5	jeden	0	2
	čtyři	3	−1	jeden	0

Chování s negativními cykly

Záporný cyklus je cyklus, jehož součet hran je záporný. Mezi žádnou dvojicí vrcholů , , které jsou součástí záporného cyklu, neexistuje nejkratší cesta, protože délka cesty od do může být libovolně malá (záporná). Pro numericky smysluplný výstup předpokládá Floyd-Warshall algoritmus, že neexistují žádné negativní cykly. Pokud však existují negativní cykly, lze k jejich detekci použít Floyd-Warshall algoritmus. Algoritmus je samozřejmě následující: $i$ $j$ $i$ $j$

Algoritmus Floyd-Warshall se iterativně dívá na délku cesty

mezi všemi páry vrcholů , včetně těch, kde ; $(i,j)$ $i=j$

Zpočátku je délka cesty nulová; $(i,i)$
Cesta se může zlepšit pouze tehdy, je-li její délka $[i,k,\ldots ,i]$

méně než nula, tzn. označuje negativní cyklus;

Po algoritmu tedy bude záporné, pokud $(i,i)$

existuje cesta záporné délky od do . $i$ $i$

Pro detekci negativních cyklů pomocí Floyd-Warshallova algoritmu je tedy možné zkontrolovat úhlopříčku matice nejkratší cesty a přítomnost záporného čísla znamená, že graf obsahuje alespoň jeden negativní cyklus. Během provádění algoritmu, pokud dojde k zápornému cyklu, se mohou objevit exponenciálně velká čísla až , kde je největší absolutní hodnota záporné hrany v grafu. Abyste se vyhnuli problémům s přetečením/podtečením, měli byste zkontrolovat záporná čísla na diagonále matice nejkratší cesty uvnitř vnitřní smyčky for algoritmu. Je zřejmé, že v neorientovaném grafu záporná hrana vytváří negativní cyklus (tj. uzavřený okruh) včetně jeho dopadajících vrcholů. Pokud vezmeme v úvahu všechny hrany výše uvedeného příkladu grafu jako neorientované, například posloupnost vrcholů 4 - 2 - 4 je cyklus se součtem vah -2. $\Omega (\cdot 6^{n-1}w_{max})$ ${\displaystyle w_{max))$

Rekonstrukce tratí

Algoritmus Floyd-Warshall obvykle poskytuje pouze délky cest mezi všemi páry vrcholů. Jednoduchými úpravami lze vytvořit metodu pro rekonstrukci skutečné cesty mezi libovolnými dvěma vrcholy koncových bodů. I když někdo může mít sklon uložit 3 skutečné cesty z každého vrcholu do každého druhého vrcholu, není to nutné a ve skutečnosti je to z hlediska paměti velmi drahé. Místo toho lze pro každý uzel v čase vypočítat strom nejkratší cesty pomocí paměti k uložení každého stromu, což nám umožňuje efektivně rekonstruovat cestu z libovolných dvou spojených vrcholů. $\Theta (|E|)$ $\Theta (|V|)$

Pseudokód [1]

nechť dist je pole minimálních vzdáleností inicializované na (nekonečno) nechť next je pole indexů vrcholů inicializované na null

|V|\times |V|

\infty

|V|\times |V|

procedure FloydWarshallWithPathReconstruction () je pro každou hranu (u, v) do dist[u][v] ← w(u, v) // Váha hrany (u, v) další[u][v] ← v pro každý vrchol v do dist[ v ][ v ] ← 0 další[v][v] ← v pro k od 1 do |V| do // standardní implementace Floyd-Warshallova algoritmu pro i od 1 do |V| pro j od 1 do |V| if dist[i][j] > dist[i][k] + dist[k][j] pak dist[i][j] ← dist[i][k] + dist[k][j] další[i][j] ← další[i][k] procedura Path(u, v) if next[u][v] = null then return [] cesta = [u] zatímco u ≠ v u ← další[u][v] cesta připojit(u) zpáteční cesta

Analýza složitosti algoritmu

Nechť je počet vrcholů. K nalezení všech ( pro všechny a ) z vyžaduje operace. Protože začínáme a počítáme posloupnost matic , , , , celkový počet použitých operací je . Proto je složitost algoritmu . $n$ $|V|$ $n^{2}$ $\mathrm {shortestPath} (i,j,k)$ $i$ $j$ $\mathrm {shortestPath} (i,j,k-1)$ $2n^{2}$ $\mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)$ $n$ $\mathrm {shortestPath} (i,j,1)$ $\mathrm {shortestPath} (i,j,2)$ $\ldots$ $\mathrm {shortestPath} (i,j,n)$ ${\displaystyle n\cdot 2n^{2}=2n^{3))$

Aplikace a zobecnění

Algoritmus Floyd-Warshall lze použít k řešení následujících problémů, zejména:

Nejkratší cesty v orientovaných grafech (Floydův algoritmus).
Tranzitivní uzávěr orientovaných grafů (Warshallův algoritmus). V původní formulaci Warshallova algoritmu je graf nevážený a je reprezentován booleovskou maticí sousednosti. Operace sčítání je pak nahrazena logickou konjunkcí (AND) a minimální operace je nahrazena logickou disjunkcí (OR).
Nalezení regulárního výrazu označujícího regulární jazyk akceptovaný konečným automatem ( Kleeneův algoritmus , úzce související zobecnění Floyd-Warshallova algoritmu)
Inverze reálné matice ( algoritmus Gauss–Jordan )
Optimální směrování. V této aplikaci musíte najít cestu s maximálním průtokem mezi dvěma vrcholy. To znamená, že místo minima, jako ve výše uvedeném pseudokódu, se použijí maxima. Váhy hran představují pevná omezení toku. Váhy cest jsou úzká hrdla, takže operace sčítání výše je nahrazena operací minima.
Rychlý výpočet sítí Pathfinder .
Nejširší cesty/cesty s maximální propustností
Výpočet kanonické formy rozdílových hraničních matic (DBM)
Výpočet podobnosti mezi grafy

Implementace

Pro C++ v knihovně boost::graph
Pro C# v QuickGraph
Pro C# v QuickGraphPCL (fork QuickGraph s lepší kompatibilitou s projekty využívajícími Portable Class Libraries.)
Pro Javu v knihovně Apache Commons Graph Library
Pro JavaScript v knihovně Cytoscape
Pro MATLAB v balíčku Matlab_bgl
Pro Perl v modulu Graph
Pro Python v knihovně SciPy (modul scipy.sparse.csgraph ) nebo v knihovně NetworkX
Pro R v balení e1071 a Rfast

Porovnání s jinými algoritmy

Floyd-Warshallův algoritmus je účinný pro výpočet všech nejkratších cest v hustých grafech , když je mezi páry vrcholů mnoho párů hran. V případě řídkých grafů s hranami nezáporné váhy je nejlepší volbou použít Dijkstrův algoritmus pro každý možný uzel. S touto volbou je složitost při použití binární haldy , která je lepší než algoritmus Floyd-Warshall, když je výrazně menší (podmínka řídkosti grafu). Pokud je graf řídký, má hrany se zápornou váhou a nejsou zde žádné cykly se zápornou celkovou váhou, pak se použije Johnsonův algoritmus , který má stejnou složitost jako varianta s Dijkstrovým algoritmem. $O(|V|\cdot |E|\log |V|)$ $O(|V|^{3})$ $|E|$ $|V|^{2}$

Známé jsou také algoritmy využívající algoritmy rychlého násobení matic , které urychlují výpočty v hustých grafech, ale obvykle mají další omezení (například reprezentovat váhy hran jako malá celá čísla) [2] [3] . Zároveň se díky velkému konstantnímu faktoru doby běhu výpočetní výhoda oproti algoritmu Floyd–Warshall projevuje pouze na velkých grafech.

Poznámky

↑ Kniha algoritmů zdarma . Získáno 19. prosince 2020. Archivováno z originálu dne 12. ledna 2021. (neurčitý)
↑ Zwick, Uri (květen 2002), Nejkratší cesty všech párů pomocí přemosťovacích sad a násobení obdélníkové matice , Journal of the ACM vol. 49 (3): 289–317 , DOI 10.1145/567112.567114 .
↑ Chan, Timothy M. (leden 2010), More algorithms for all-pairests shortest paths in weighted graphs , SIAM Journal on Computing Vol. 39 (5): 2075–2089 , DOI 10.1137/08071990x .

Literatura

Levitin A. V. Kapitola 11. Překonávání omezení: Metoda půlení // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 349-353. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M. : Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .
Belousov A. I., Tkachev S. B. Diskrétní matematika. - M. : MGTU, 2006. - 744 s. — ISBN 5-7038-2886-4 .
https://cs.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Algoritmy 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	Alfa beta výstřižek 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