Algoritmus Floyd – Warshall - Floyd–Warshall algorithm

Algoritmus Floyd – Warshall

Třída	Problém s nejkratší cestou všech párů (pro vážené grafy)
Datová struktura	Graf
Nejhorší výkon	${\ displaystyle \ Theta (| V |^{3})}$
Nejlepší výkon	${\ displaystyle \ Theta (| V |^{3})}$
Průměrný výkon	${\ displaystyle \ Theta (| V |^{3})}$
Nejhorší prostorová složitost	${\ displaystyle \ Theta (| V |^{2})}$

V informatice je Floyd – Warshallův algoritmus (také známý jako Floydův algoritmus , Roy – Warshallův algoritmus , Roy – Floydův algoritmus nebo algoritmus WFI ) algoritmus pro hledání nejkratších cest v orientovaném váženém grafu s kladnou nebo zápornou hranou váhy (ale bez negativních cyklů). Jediným provedením algoritmu se zjistí délky (součtové hmotnosti) nejkratších cest mezi všemi páry vrcholů. Přestože nevrací podrobnosti o samotných cestách, je možné cesty rekonstruovat jednoduchými úpravami algoritmu. Verze algoritmu lze také použít k nalezení přechodného uzavření vztahu nebo (ve spojení s hlasovacím systémem Schulze ) nejširších cest mezi všemi páry vrcholů ve váženém grafu. ${\ displaystyle R}$

Historie a pojmenování

Algoritmus Floyd – Warshall je příkladem dynamického programování a byl publikován ve své aktuálně uznávané podobě Robertem Floydem v roce 1962. Je však v podstatě stejný jako algoritmy, které dříve publikoval Bernard Roy v roce 1959 a také Stephen Warshall v roce 1962 pro nalezení tranzitivního uzavření grafu a je v těsném spojení s Kleeneovým algoritmem (publikovaným v roce 1956) pro převod deterministického konečného automatu na regulární výraz . Moderní formulaci algoritmu jako tří vnořených smyček poprvé popsal Peter Ingerman, také v roce 1962.

Algoritmus

Algoritmus Floyd – Warshall porovnává všechny možné cesty v grafu mezi každou dvojicí vrcholů. Dokáže to pomocí srovnání v grafu, přestože v grafu může být až hran a testuje se každá kombinace hran. Činí tak postupným zlepšováním odhadu na nejkratší cestě mezi dvěma vrcholy, dokud není odhad optimální. ${\ displaystyle \ Theta (| V |^{3})}$${\ displaystyle \ Omega (| V |^{2})}$

Zvažte graf s vrcholy očíslovanými od 1 do  . Dále zvažte funkci, která vrací nejkratší možnou cestu z do pomocí vrcholů pouze ze sady jako mezilehlých bodů na cestě. Vzhledem k této funkci je nyní naším cílem najít nejkratší cestu od každého ke každému pomocí libovolného vrcholu v . ${\ displaystyle G}$${\ displaystyle V}$${\ displaystyle N}$${\ displaystyle \ mathrm {shortestPath} (i, j, k)}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle \ {1,2, \ ldots, k \}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle \ {1,2, \ ldots, N \}}$

Pro každý z těchto párů vrcholů může být buď ${\ displaystyle \ mathrm {shortestPath} (i, j, k)}$

(1) cesta, která neprochází (používá pouze vrcholy v sadě .)${\ displaystyle k}$${\ Displaystyle \ {1, \ ldots, k-1 \}}$

nebo

(2) cesta, která prochází (od do a poté od do , oba pouze pomocí mezilehlých vrcholů v  )${\ displaystyle k}$${\ displaystyle i}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle j}$${\ Displaystyle \ {1, \ ldots, k-1 \}}$

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

Pokud je váha hrany mezi vrcholy a , můžeme definovat pomocí následujícího rekurzivního vzorce: základní případ je ${\ Displaystyle w (i, j)}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle \ mathrm {shortestPath} (i, j, k)}$

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

a rekurzivní případ je

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

${\ Displaystyle \ 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 je srdcem algoritmu Floyd -Warshall. Algoritmus funguje tak, že nejprve vypočítá pro všechny páry pro , potom a tak dále. Tento proces pokračuje, dokud jsme nenašli nejkratší cestu pro všechny páry pomocí jakýchkoli mezilehlých vrcholů. Následuje pseudokód pro tuto základní verzi: ${\ displaystyle \ mathrm {shortestPath} (i, j, k)}$${\ displaystyle (i, j)}$${\ displaystyle k = 1}$${\ displaystyle k = 2}$${\ displaystyle k = N}$${\ displaystyle (i, j)}$

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

Příklad

Algoritmus výše je proveden na grafu vlevo dole:

Před první rekurzí vnější smyčky, označené výše k = 0 , odpovídají jediné známé cesty jednotlivým hranám v grafu. Při k = 1 jsou nalezeny cesty, které procházejí vrcholem 1: zejména je nalezena cesta [2,1,3], která nahrazuje cestu [2,3], která má méně hran, ale je delší (pokud jde o hmotnost ). Při k = 2 jsou nalezeny cesty procházející vrcholy {1,2}. Červené a modré pole ukazuje, jak je cesta [4,2,1,3] sestavena ze dvou známých cest [4,2] a [2,1,3], se kterými se setkáváme v předchozích iteracích, přičemž 2 jsou v průsečíku. Cesta [4,2,3] není brána v úvahu, protože [2,1,3] je dosud nejkratší cestou od 2 do 3. Při k = 3 cesty procházející vrcholy {1,2,3} Jsou nalezeny. Nakonec při k = 4 jsou nalezeny všechny nejkratší cesty.

Matice vzdálenosti při každé iteraci k , s aktualizovanými vzdálenostmi tučně , bude:

Chování s negativními cykly

Negativní cyklus je cyklus, jehož hrany se sčítají se zápornou hodnotou. Mezi dvojicí vrcholů , které jsou součástí negativního cyklu, neexistuje nejkratší cesta , protože délky cest od do mohou být libovolně malé (záporné). U číselně smysluplného výstupu algoritmus Floyd – Warshall předpokládá, že neexistují žádné negativní cykly. Pokud však existují negativní cykly, lze k jejich detekci použít algoritmus Floyd – Warshall. Intuice je následující: ${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle j}$

• Algoritmus Floyd – Warshall iterativně reviduje délky dráhy mezi všemi páry vrcholů , včetně kde ;${\ displaystyle (i, j)}$${\ displaystyle i = j}$
• Zpočátku je délka cesty nulová;${\ displaystyle (i, i)}$
• Cesta se na tom může zlepšit, pouze pokud má délku menší než nula, tj. Označuje negativní cyklus;${\ Displaystyle [i, k, \ ldots, i]}$
• Po algoritmu tedy bude záporné, pokud existuje cesta záporné délky zezadu do .${\ displaystyle (i, i)}$${\ displaystyle i}$${\ displaystyle i}$

K detekci negativních cyklů pomocí algoritmu Floyd -Warshall lze tedy zkontrolovat úhlopříčku matice dráhy a přítomnost záporného čísla naznačuje, že graf obsahuje alespoň jeden negativní cyklus. Pokud během provádění algoritmu existuje záporný cyklus, mohou se objevit exponenciálně velká čísla, stejně velká jako 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 úhlopříčce matice cesty ve vnitřní smyčce for algoritmu. Je zřejmé, že v neorientovaném grafu vytváří negativní hrana negativní cyklus (tj. Uzavřená procházka) zahrnující jeho dopadající vrcholy. Vzhledem k tomu, že všechny hrany výše uvedeného příkladového grafu jsou neorientované, např. Vrcholová posloupnost 4 - 2 - 4 je cyklus se součtem hmotnosti −2. ${\ displaystyle \ Omega (\ cdot 6^{n-1} w_ {max})}$${\ displaystyle w_ {max}}$

Rekonstrukce cesty

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

Pseudo kód

let dist be a ${\displaystyle |V|\times |V|}$ array of minimum distances initialized to ${\displaystyle \infty }$ (infinity)
let next be a ${\displaystyle |V|\times |V|}$ array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
        next[u][v] ← v
    for each vertex v do
        dist[v][v] ← 0
        next[v][v] ← v
    for k from 1 to |V| do // standard Floyd-Warshall implementation
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][j] > dist[i][k] + dist[k][j] then
                    dist[i][j] ← dist[i][k] + dist[k][j]
                    next[i][j] ← next[i][k]

procedure Path(u, v)
    if next[u][v] = null then
        return []
    path = [u]
    while u ≠ v
        u ← next[u][v]
        path.append(u)
    return path

Analýza

Dovolit být počet vrcholů. Chcete-li najít vše o (pro všechny a ) od těch vyžaduje operace. Vzhledem k tomu, začneme a spočítat pořadí matic , , , celkový počet operací používá . Proto je složitost algoritmu je . ${\ displaystyle n}$${\ displaystyle | V |}$${\ displaystyle n^{2}}$${\ displaystyle \ mathrm {shortestPath} (i, j, k)}$${\ displaystyle i}$${\ displaystyle j}$${\ Displaystyle \ mathrm {shortestPath} (i, j, k-1)}$${\ displaystyle 2n^{2}}$${\ Displaystyle \ mathrm {shortestPath} (i, j, 0) = \ mathrm {edgeCost} (i, j)}$${\ displaystyle n}$${\ displaystyle \ mathrm {shortestPath} (i, j, 1)}$${\ displaystyle \ mathrm {shortestPath} (i, j, 2)}$${\ displaystyle \ ldots}$${\ displaystyle \ mathrm {shortestPath} (i, j, n)}$${\ Displaystyle n \ cdot 2n^{2} = 2n^{3}}$${\ displaystyle \ Theta (n^{3})}$

Aplikace a zobecnění

Algoritmus Floyd – Warshall lze použít mimo jiné k řešení následujících problémů:

• Nejkratší cesty v orientovaných grafech (Floydův algoritmus).
• Přechodné uzavření směrovaných grafů (Warshallův algoritmus). V Warshallově původní formulaci algoritmu je graf nevážený a reprezentovaný booleovskou maticí sousednosti . Poté je operace sčítání nahrazena logickou spojkou (AND) a minimální operace 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í generalizace Floyd -Warshallova algoritmu)
• Inverze z reálných matic ( Gauss-Jordán algoritmus )
• Optimální směrování. V této aplikaci se člověk zajímá o nalezení cesty s maximálním průtokem mezi dvěma vrcholy. To znamená, že místo přijímání minim jako ve výše uvedeném pseudokódu se místo toho berou maxima. Okrajová závaží představují pevná omezení průtoku. Váhy cesty představují úzká místa; výše uvedená operace sčítání je nahrazena minimální operací.
• Rychlý výpočet sítí Pathfinder .
• Nejširší cesty/Cesty maximální šířky pásma
• Výpočet kanonické formy rozdílově vázaných matic (DBM)
• Výpočet podobnosti mezi grafy
• Přechodné uzavření v AND/OR/prahových grafech.

Implementace

Implementace jsou k dispozici pro mnoho programovacích jazyků .

• Pro C ++ v knihovně boost :: graph
• Pro C# v QuickGraph
• Pro C# v QuickGraphPCL (vidlice QuickGraph s lepší kompatibilitou s projekty využívajícími knihovny přenosných tříd.)
• Pro Javu v knihovně Apache Commons Graph
• 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 knihovně NetworkX
• Pro R , v balíčcích e1071 a Rfast

Porovnání s jinými algoritmy nejkratších cest

Algoritmus Floyd – Warshall je dobrou volbou pro výpočet cest mezi všemi páry vrcholů v hustých grafech , ve kterých je většina nebo všechny páry vrcholů spojeny hranami. U řídkých grafů s nezápornými váhovými hranami lze dosáhnout nižší asymptotické složitosti spuštěním Dijkstraova algoritmu z každého možného počátečního vrcholu, protože doba nejhoršího případu opakování Dijkstra ( pomocí haldy Fibonacci ) je menší než doba běhu Floyd –Warshallův algoritmus, když je výrazně menší než . Pro řídké grafy s negativními hranami, ale bez negativních cyklů, lze použít Johnsonův algoritmus se stejnou asymptotickou dobou běhu jako opakovaný Dijkstra přístup. ${\ Displaystyle O (| E || V |+| V |^{2} \ log | V |)}$${\ displaystyle O (| V |^{3})}$${\ displaystyle | E |}$${\ displaystyle | V |^{2}}$

Existují také známé algoritmy využívající rychlé násobení matic ke zrychlení výpočtu nejkratší cesty všech párů v hustých grafech, ale ty obvykle vytvářejí další předpoklady o hraničních váhách (například vyžadují, aby to byla malá celá čísla). Kromě toho by kvůli vysokým konstantním faktorům v jejich době běhu poskytovaly zrychlení přes algoritmus Floyd – Warshall pouze pro velmi velké grafy.

Reference

externí odkazy

• Interaktivní animace algoritmu Floyd – Warshall
• Interaktivní animace algoritmu Floyd – Warshall (Technická univerzita v Mnichově)