Floyd-Warshall algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 april 2020; kontroller kräver 13 redigeringar .

Floyd-Warshall algoritm

Döpt efter	Robert Floyd och Stephen Warshall
Författare	Bernard Roy [d]
ändamål	sök i en graf efter kortaste vägarna mellan valfritt par av hörn
Datastruktur	Graf
värsta tiden	$\Theta (\|V\|^{3})$
Lämpligast tid	$\Theta (\|V\|^{3})$
Snittid	$\Theta (\|V\|^{3})$
Minneskostnad	$\Theta (\|V\|^{2})$
Mediafiler på Wikimedia Commons

Inom datavetenskap är Floyd–Warshall-algoritmen (även känd som Floyd -algoritmen , Roy–Warshall-algoritmen , Roy–Floyd- algoritmen eller WFI-algoritmen ) en algoritm för att hitta kortaste vägarna i en viktad graf med positiva eller negativa kantvikter (men inga negativa cykler). I en exekvering av algoritmen kommer längderna (totalvikterna) av de kortaste vägarna mellan alla hörnpar att hittas. Även om det inte returnerar detaljerna för själva vägarna, är det möjligt att rekonstruera vägarna med enkla modifieringar av algoritmen. Varianter av algoritmen kan också användas för att hitta den transitiva stängningen av relationen $R$ eller (i samband med Schulzes röstsystem ) de bredaste vägarna mellan alla hörnpar i en viktad graf.

Historik och namngivning

Floyd-Warshall-algoritmen är ett exempel på dynamisk programmering och publicerades i sin nu accepterade form av Robert Floyd 1962. Det är dock i huvudsak samma som de algoritmer som tidigare publicerades av Bernard Roy 1959 och även av Stephen Warshall 1962 för att hitta den transitiva stängningen av en graf, och är nära besläktad med Kleenes algoritm (publicerad 1956) för att konvertera en deterministisk ändlig automat till reguljärt uttryck . Den moderna formuleringen av algoritmen i form av tre kapslade för loopar beskrevs först av Peter Ingerman också 1962

Algoritm

Betrakta en graf med hörn numrerade från 1 till . Floyd-Warshall-algoritmen jämför alla möjliga vägar genom grafen mellan varje par av hörn. Det kan göra detta för jämförelser i grafen, även om grafen kan ha upp till kanter, och varje kombination av kanter kontrolleras. Detta uppnås genom att gradvis förbättra den kortaste väguppskattningen mellan två hörn tills uppskattningen är optimal. $G$ $V$ $N$ $\Theta (|V|^{3})$ $\Omega (|V|^{2})$

Överväg sedan en funktion som returnerar den kortaste möjliga vägen från till att endast använda hörn från mängden som mellanliggande punkter längs denna väg. Nu, givet den här funktionen, är vårt mål att hitta den kortaste vägen från var och en till varje , med hjälp av valfri vertex i . $\mathrm {shorttestPath} (i,j,k)$ $i$ $j$ ${\displaystyle \{1,2,\ldots ,k\))$ $i$ $j$ $\{1,2,\ldots ,N\}$

För vart och ett av dessa par av hörn kan det finnas antingen $\mathrm {shorttestPath} (i,j,k)$

(1) en väg som inte går igenom (använder endast hörn från uppsättningen ),

k

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

eller

(2) en väg som går igenom (från till och sedan från till , i båda fallen används endast mellanliggande hörn i ).

k

i

k

k

j

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

Vi vet att den bästa vägen från till , vilket är den väg som endast använder hörn c till , definieras som , och det är klart att om det fanns en bättre väg från till till , så skulle längden på denna väg vara en kedja bestående av av den kortaste vägen från till (endast med mellanliggande hörn i ) och den kortaste vägen från till (endast med mellanliggande hörn i ). $i$ $j$ $ett$ $k-1$ $\mathrm {shorttestPath} (i,j,k-1)$ $i$ $k$ $j$ $i$ $k$ $\{1,\ldots ,k-1\}$ $k$ $j$ $\{1,\ldots ,k-1\}$

Om är vikten av en kant mellan hörn och , kan vi definiera den i termer av följande rekursiva formel: $w(i,j)$ $i$ $j$ $\mathrm {shorttestPath} (i,j,k)$

basfallet

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

och rekursivt fall

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

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

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

Denna formel utgör grunden för Floyd-Warshall-algoritmen. Algoritmen fungerar genom att först beräkna alla par för , och sedan , och så vidare. Denna process fortsätter tills den kortaste vägen hittas för alla par som använder mellanliggande hörn. Pseudokoden för denna basversion är följande: $\mathrm {shorttestPath} (i,j,k)$ $(I j)$ $k=1$ $k=2$ $k=N$ $(I j)$

låt dist vara en |V| × |V| array av minimiavstånd initialiserade som ∞ (oändligt) för varje kant ( u , v ) do dist[ u ][ v ] ← w( u , v ) // Kantens vikt ( u , v ) för varje vertex v do dist[ v ][ v ] ← 0 för k från 1 till |V| för i från 1 till |V| för j från 1 till |V| if dist[ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ] dist[ i ][ j ] ← dist[ i ][ k ] + dist[ k ][ j ] slut om

Exempel

Algoritmen ovan exekveras på grafen längst ner till vänster:

Fram till den första rekursionen av den yttre slingan, ovan betecknad med k = 0, motsvarar de enda kända banorna individuella kanter i grafen. För k = 1 hittas banor som passerar genom vertex 1: i synnerhet hittas banan [2,1,3], som ersätter banan [2,3], som har färre kanter men är längre (i viktmässigt hänseende) ). För k = 2 hittas banor som passerar genom hörn 1,2. De röda och blå rutorna visar hur banan [4,2,1,3] är sammansatt av de två kända banorna [4,2] och [2,1,3] som påträffats i tidigare iterationer, med 2 i korsningen. Vägen [4,2,3] beaktas inte eftersom [2,1,3] är den kortaste vägen hittills från 2 till 3. För k = 3 hittas vägar som passerar genom hörn 1,2,3. Slutligen, för k = 4, hittas alla kortaste vägar.

Avståndsmatrisen vid varje iteration k, uppdaterade avstånd i fet stil , kommer att vara:

k = 0		ett	2	3	fyra
k = 0		j
i	ett	0	∞	−2	∞
	2	fyra	0	3	∞
	3	∞	∞	0	2
	fyra	∞	−1	∞	0

k = 1		ett	2	3	fyra
k = 1		j
i	ett	0	∞	−2	∞
	2	fyra	0	2	∞
	3	∞	∞	0	2
	fyra	∞	−1	∞	0

k = 2		ett	2	3	fyra
k = 2		j
i	ett	0	∞	−2	∞
	2	fyra	0	2	∞
	3	∞	∞	0	2
	fyra	3	−1	ett	0

k = 3		ett	2	3	fyra
k = 3		j
i	ett	0	∞	−2	0
	2	fyra	0	2	fyra
	3	∞	∞	0	2
	fyra	3	−1	ett	0

k = 4		ett	2	3	fyra
k = 4		j
i	ett	0	−1	−2	0
	2	fyra	0	2	fyra
	3	5	ett	0	2
	fyra	3	−1	ett	0

Beteende med negativa cykler

En negativ cykel är en cykel vars kantsumma är negativ. Det finns ingen kortaste väg mellan något par av hörn , , som är en del av en negativ cykel, eftersom längden på vägen från till kan vara godtyckligt liten (negativ). För numeriskt meningsfull utdata antar Floyd–Warshall-algoritmen att det inte finns några negativa cykler. Men om det finns negativa cykler kan Floyd-Warshall-algoritmen användas för att upptäcka dem. Uppenbarligen är algoritmen följande: $i$ $j$ $i$ $j$

Floyd-Warshall-algoritmen tittar iterativt på väglängden

mellan alla par av hörn , inklusive de där ; $(I j)$ $i=j$

Initialt är väglängden noll; $(i,i)$
En väg kan bara förbättras om dess längd är $[i,k,\ldots ,i]$

mindre än noll, dvs. betecknar en negativ cykel;

Således, efter algoritmen, kommer att vara negativ om $(i,i)$

det finns en väg med negativ längd från till . $i$ $i$

För att upptäcka negativa cykler med Floyd-Warshall-algoritmen kan man därför kontrollera diagonalen för den kortaste vägmatrisen, och närvaron av ett negativt tal indikerar att grafen innehåller minst en negativ cykel. Under exekveringen av algoritmen, om det finns en negativ cykel, kan exponentiellt stora tal dyka upp, upp till , där är det största absoluta värdet av en negativ kant i grafen. För att undvika problem med spill/underflöde bör du kontrollera om det finns negativa tal på diagonalen för den kortaste vägmatrisen inuti algoritmens inre for-loop. Uppenbarligen, i en oriktad graf, skapar en negativ flank en negativ cykel (det vill säga en sluten krets) inklusive dess infallande hörn. Om man betraktar alla kanter på grafexemplet ovan som oriktade, till exempel är sekvensen av hörn 4 - 2 - 4 en cykel med viktsumman - 2. $\Omega (\cdot 6^{n-1}w_{max})$ ${\displaystyle w_{max))$

Rekonstruktion av spår

Floyd-Warshall-algoritmen ger vanligtvis bara väglängder mellan alla par av hörn. Med enkla modifieringar kan en metod skapas för att rekonstruera den faktiska vägen mellan två valfria ändpunktspunkter. Även om man kan vara benägen att lagra 3 faktiska vägar från varje vertex till vartannat vertex, är detta inte nödvändigt och är faktiskt mycket dyrt i termer av minne. Istället kan ett kortaste vägträd beräknas för varje nod i tid, med hjälp av minne för att lagra varje träd, vilket gör att vi effektivt kan rekonstruera en väg från två anslutna hörn. $\Theta (|E|)$ $\Theta (|V|)$

Pseudokod [1]

låt dist vara en matris med minsta avstånd initierad till (oändlighet) låt nästa vara en matris med vertexindex initierade till null

|V|\times |V|

\infty

|V|\times |V|

procedur FloydWarshallWithPathReconstruction () är för varje kant (u, v) do dist[u][v] ← w(u, v) // Kantens vikt (u, v) nästa[u][v] ← v för varje vertex v do dist[ v ][ v ] ← 0 nästa[v][v] ← v för k från 1 till |V| gör // standardimplementering av Floyd-Warshall-algoritmen för i från 1 till |V| för j från 1 till |V| om dist[i][j] > dist[i][k] + dist[k][j] då dist[i][j] ← dist[i][k] + dist[k][j] nästa[i][j] ← nästa[i][k] procedure Path(u, v) om nästa[u][v] = null returnera sedan [] sökväg = [u] medan u ≠ v u ← nästa[u][v] sökväg append(u) returväg _

Komplexitetsanalys av algoritmen

Låt vara antalet hörn. För att hitta alla ( för alla och ) kräver operationer. Eftersom vi börjar med och beräknar sekvensen av matriser , , , , är det totala antalet operationer som används . Därför är komplexiteten för algoritmen . $n$ $|V|$ $n^{2}$ $\mathrm {shorttestPath} (i,j,k)$ $i$ $j$ $\mathrm {shorttestPath} (i,j,k-1)$ $2n^{2}$ $\mathrm {shorttestPath} (i,j,0)=\mathrm {edgeCost} (i,j)$ $n$ $\mathrm {shorttestPath} (i,j,1)$ $\mathrm {shorttestPath} (i,j,2)$ $\ldots$ $\mathrm {shorttestPath} (i,j,n)$ ${\displaystyle n\cdot 2n^{2}=2n^{3))$

Applikationer och generaliseringar

Floyd-Warshall-algoritmen kan användas för att lösa följande problem, särskilt:

Kortaste vägarna i riktade grafer (Floyds algoritm).
Transitiv stängning av riktade grafer (Warshalls algoritm). I den ursprungliga formuleringen av Warshalls algoritm är grafen oviktad och representeras av en boolesk närliggande matris. Adderingsoperationen ersätts sedan av en logisk konjunktion (AND), och den minimala operationen ersätts av en logisk disjunktion (OR).
Att hitta ett reguljärt uttryck som betecknar ett reguljärt språk som accepteras av en finit automat ( Kleenes algoritm , en närbesläktad generalisering av Floyd–Warshall-algoritmen)
Real Matrix Inversion ( Gauss–Jordan algorithm )
Optimal routing. I den här applikationen måste du hitta vägen med det maximala flödet mellan två hörn. Det betyder att istället för att ta minimivärden, som i pseudokoden ovan, används maximum. Kantvikterna representerar de fasta begränsningarna för flödet. Banvikter är flaskhalsar så additionsoperationen ovan ersätts av minimioperationen.
Snabb beräkning av Pathfinder-nätverk .
Bredaste vägar/Maximum genomströmningsvägar
Beräkna den kanoniska formen av skillnadsgränsmatriser (DBM)
Beräkningslikhet mellan grafer

Implementeringar

För C++ , i boost::graph- biblioteket
För C# , i QuickGraph
För C# , i QuickGraphPCL (En gaffel av QuickGraph med bättre kompatibilitet med projekt som använder Portable Class Libraries.)
För Java , i Apache Commons Graph Library
För JavaScript , i Cytoscape- biblioteket
För MATLAB , i paketet Matlab_bgl
För Perl , i Graph -modulen
För Python , i SciPy- biblioteket (modul scipy.sparse.csgraph ) eller i NetworkX- biblioteket
För R , i paket e1071 och Rfast

Jämförelse med andra algoritmer

Floyd-Warshall-algoritmen är effektiv för att beräkna alla kortaste vägar i täta grafer när det finns många par av kanter mellan par av hörn. I fallet med glesa grafer med kanter av icke-negativ vikt är det bästa valet att använda Dijkstras algoritm för varje möjlig nod. Med detta val är komplexiteten när man använder en binär hög , vilket är bättre än Floyd-Warshall-algoritmen när den är betydligt mindre (grafens sparsitetsvillkor). Om grafen är gles, den har kanter med negativ vikt och det inte finns några cykler med negativ totalvikt, då används Johnson-algoritmen , som har samma komplexitet som varianten med Dijkstras algoritm. $O(|V|\cdot |E|\log |V|)$ $O(|V|^{3})$ $|E|$ $|V|^{2}$

Algoritmer som använder snabba matrismultiplikationsalgoritmer är också kända , som påskyndar beräkningar i täta grafer, men de har vanligtvis ytterligare begränsningar (till exempel representerar kantvikter som små heltal) [2] [3] . Samtidigt, på grund av den stora konstanta körtidsfaktorn, visas beräkningsfördelen gentemot Floyd–Warshall-algoritmen endast på stora grafer.

Anteckningar

↑ Gratis algoritmbok . Hämtad 19 december 2020. Arkiverad från originalet 12 januari 2021. (obestämd)
↑ Zwick, Uri (maj 2002), Alla parar kortaste vägar med användning av överbryggande uppsättningar och rektangulär matrismultiplikation , Journal of the ACM vol. 49 (3): 289–317 , DOI 10.1145/567112.567114 .
↑ Chan, Timothy M. (januari 2010), Fler algoritmer för alla pars kortaste vägar i viktade grafer , SIAM Journal on Computing Vol. 39 (5): 2075–2089 , DOI 10.1137/08071990x .

Litteratur

Levitin A. V. Kapitel 11. Att övervinna begränsningar: Bisektionsmetoden // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 349-353. — 576 sid. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M. : Williams", 2006. - S. 1296. - ISBN 0-07-013151-1 .
Belousov A. I., Tkachev S. B. Diskret matematik. - M. : MGTU, 2006. - 744 sid. — ISBN 5-7038-2886-4 .
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare