Floyd–Warshall-algoritmus forrásának megtekintése

{{Algoritmus infobox
|név                          = Floyd–Warshall-algoritmus
|kategória                    = [[Legrövidebb út probléma]] (súlyozott gráfok esetében)
|adatstruktúra                = [[Gráf]]
|legrosszabb idő bonyolultság = <math>\Theta (|V|^3)</math>
|legjobb idő bonyolultság     = <math>\Theta (|V|^3)</math>
|átlagos idő bonyolultság     = <math>\Theta (|V|^3)</math>
|legrosszabb tár bonyolultság = <math>\Theta (|V|^2)</math>
}}

A [[Számítástudomány|számítástechnikában]] a '''Floyd–Warshall-algoritmus''' (más néven '''Floyd–algoritmus''', a '''Roy–Warshall-algoritmus''', a '''Roy–Floyd-algoritmus''' vagy az ún. '''WFI-algoritmus''' ) egy olyan [[algoritmus]], amely a megtalálja [[Legrövidebb út probléma|legrövidebb útvonalakat]]  egy pozitív vagy negatív élsúlyú [[Gráfelméleti fogalomtár|súlyozott gráfban]] . (de negatív körök nélkül).<ref>Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. {{ISBN|0-262-03141-8}}. See in particular Section 26.2, "The Floyd–Warshall algorithm", pp. 558–565 and Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576.</ref><ref>{{Hivatkozás/Könyv |last=Kenneth H. Rosen |title=Discrete Mathematics and Its Applications, 5th Edition |year=2003 |publisher=Addison Wesley |isbn=978-0-07-119881-3}}</ref> Az algoritmus egyetlen végrehajtása megtalálja az összes csúcspár közötti legrövidebb távolságok hosszát (összesített súlyát). Annak ellenére, hogy nem adja vissza az útvonalak részleteit, lehetséges az útvonalak rekonstruálása az algoritmus egyszerű módosításával. Az algoritmus egyes változatai arra is használhatóak, hogy megtaláljunk egy a valós számokkal összefüggésben levő [[tranzitív lezárás]]t, vagy (a [[Schulze-módszer]]rel összefüggésben)  a [[A legszélesebb útvonal probléma|legszélesebb útvonalakat]] az összes csúcspár között egy súlyozott grafikonon.

== Előzmények és elnevezések ==
A Floyd–Warshall-algoritmus a [[dinamikus programozás]] egy jól ismert példája, melyet [[Robert W. Floyd|Robert Floyd]] publikált 1962-ben.<ref>{{Cite journal|first=Robert W.|author=Floyd|authorlink=Robert W. Floyd|title=Algorithm 97: Shortest Path|journal=[[Communications of the ACM]]|volume=5|issue=6|pages=345|date=June 1962|doi=10.1145/367766.368168}}</ref> Alapvetően megegyezik azon algoritmusokkal, melyeket korábban Bernard Roy 1959-ben kiadott<ref>{{Cite journal|first=Bernard|author=Roy|authorlink=Bernard Roy|title=Transitivité et connexité.|journal=[[C. R. Acad. Sci. Paris]]|volume=249|pages=216–218|year=1959|url=https://gallica.bnf.fr/ark:/12148/bpt6k3201c/f222.image|language=French}}
</ref> és továbbá [[Stephen Warshall]] 1962-ben <ref>{{Cite journal|first=Stephen|author=Warshall|title=A theorem on Boolean matrices|journal=[[Journal of the ACM]]|volume=9|issue=1|pages=11–12|date=January 1962|doi=10.1145/321105.321107}}</ref> egy grafikon tranzitív lezárásának a megállapítására,  és szorosan kapcsolódik Kleene algoritmusához (1956-ban lett közzétéve) amely témája egy [[Determinisztikus véges állapotú gép|determinisztikus véges automata]] konvertálása [[Reguláris kifejezés|szabályos kifejezésekké]].<ref>{{Hivatkozás/Könyv |last=Kleene |first=S. C. |authorlink=Stephen Cole Kleene |editor=[[Claude Elwood Shannon|C. E. Shannon]] and [[John McCarthy (informatikus)|J. McCarthy]] |title=Automata Studies |year=1956 |publisher=Princeton University Press |page=3–42 |chapter=Representation of events in nerve nets and finite automata}}</ref> Az algoritmus modern formuláját azaz a három egymásba ágyazott hurkot (for ciklust) először Peter Ingerman fogalmazta meg, szintén 1962-ben.<ref>{{Cite journal|first=Peter Z.|author=Ingerman|title=Algorithm 141: Path Matrix|journal=[[Communications of the ACM]]|volume=5|pages=556|date=November 1962|doi=10.1145/368996.369016}}</ref>

== Algoritmus ==
A Floyd–Warshall algoritmus összehasonlítja az összes lehetséges utat a grafikonon az egyes csúcspárok között. Képes ezt megtenni <math>\Theta(|V|^3)</math> összehasonlítással egy gráfban, bár lehet, hogy akár <math>\Omega (|V|^2)</math> él van a grafikonon, és az élek minden kombinációját szükséges tesztelni. Ez úgy történik, hogy fokozatosan javítja a becslést a két csúcs közötti legrövidebb útvonalra vonatkozóan, amíg a becslés nem lesz optimális.

Vegyünk egy <math>G</math> grafikont,<math>V</math> csúcsokkal 1-től&nbsp;<math>N</math>-ig számozva. Továbbá egy függvényt az ún. <math>\mathrm{legrovidebbUtvonal}(i ,j ,k )</math> amely visszatér a legrövidebb útvonallal  <math>i</math> és <math>j</math>  között adott csúcsok használatával: <math>\{1,2,\ldots,k\}</math> közbenső pontként a csúcsok mentén.  Figyelembe véve az adott függvényt a célunk az, hogy megtaláljuk a legrövidebb utat minden  <math>i</math> -től minden <math>j</math>-ig bármelyik csúcs használatával:  <math>\{1,2,\ldots,N\}</math>.

A csúcspárok mindegyikénél a <math>\mathrm{legrovidebbUtvonal}(i ,j ,k )</math> lehet akár

: (1) egy útvonal, amely nem megy át <math>k</math>-n (amely csak az adott csúcsokat használja: <math>\{1,\ldots,k-1\}</math>)

vagy

: (2) egy útvonal, amely végigmegy <math>k</math>-n (<math>i</math>-től <math>k</math>-ig és aztán <math>k</math>-tól <math>j</math>-ig, mindkét esetben az adott  közbenső csúcsokat használva: &nbsp;<math>\{1,\ldots,k-1\}</math>

Tudjuk, hogy a legjobb útvonal <math>i</math>-től <math>j</math>-ig az amely csak azon csúcsokat használja amik <math>1</math>-en keresztül <math>k-1</math> vannak meghatározva a <math>\mathrm{legrovidebbUtvonal}(i ,j ,k-1)</math> által, és egyértelmű, hogy ha jobb útvonal lenne <math>i</math>-től <math>k</math>-ig majd onnan <math>j</math>-ig, akkor ezen útvonalnak a hossza lenne a legrövidebb út láncolata az <math>i</math>-től a <math>k</math>-ig (csak a közbenső csúcsok használatával <math>\{1,\ldots,k-1\}</math>) és a legrövidebb a <math>k</math>-tól <math>j</math>-ig (csak a közbenső csúcsok használatával &nbsp;<math>\{1,\ldots,k-1\}</math>).

Ha <math>w(i,j)</math> az él súlya az adott <math>i</math> és <math>j</math> csúcsok között, akkor meghatározhatjuk a <math>\mathrm{legrovidebbUtvonal}(i ,j ,k )</math> függvényt a következő [[Rekurzió|rekurzív]] képlet szerint:

<math>\mathrm{legrovidebbUtvonal}(i ,j ,0 ) = w (i ,j )</math>

a rekurzív eset a következő:

: <math>\mathrm{legrovidebbUtvonal}(i,j,k) =</math>
:: <math>\mathrm{min}\Big(\mathrm{legrovidebbUtvonal}(i,j,k-1),</math>
::: <math>\mathrm{legrovidebbUtvonal}(i,k,k-1)+\mathrm{legrovidebbUtvonal}(k,j,k-1)\Big)</math>.

Ez a képlet a Floyd–Warshall algoritmus szive. Az algoritmus futása során először kiszámolja a <math>\mathrm{legrovidebbUtvonal}(i ,j ,k )</math> alapján az <math>(i,j)</math> pároknak a <math>k=1</math>, majd <math>k=2</math> és így tovább. Ez a folyamat addig folytatódik, amíg <math>k=N</math>, és megtaláltuk a legrövidebb utat mindegyik <math>(i,j)</math> páros számára bármilyen közbenső csúcs használatával. Az alapváltozat pszeudókódja a következő:

 Legyen az ún. 'tavolsag' a |V| × |V| minimális távolságok tömbje, amely inicializálva ∞-ig (végtelen)
 '''for each''' el (''u'', ''v'') '''do'''
     tavolsag[''u''][''v''] &#x2190; w(''u'', ''v'')  ''// Az adott él súlya (''u'','' v'')''
 '''for each''' csucs ''v'' '''do'''
     tavolsag[''v''][''v''] &#x2190; 0
 '''for''' ''k'' '''from''' 1 '''to''' |V|
     '''for''' ''i'' '''from''' 1 '''to''' |V|
         '''for''' ''j'' '''from''' 1 '''to''' |V|
             '''if''' tavolsag[''i''][''j''] > tavolsag[''i''][''k''] + tavolsag[''k''][''j''] 
                 tavolsag[''i''][''j''] &#x2190; tavolsag[''i''][''k''] + tavolsag[''k''][''j'']
             '''end if'''

== Példa ==
A fenti algoritmust az alább látható bal oldali grafikonon láthatjuk:

[[File:Floyd-Warshall_example.svg|600x600px]]

A külső hurok első rekurziója előtt, a fenti {{Math|1=''k'' = 0}} jelöléssel láthatjuk, az egyetlen ismert útvonalat amely megfelel a grafikon egyes széleinek. {{Math|1=''k'' = 1}} esetén mindössze 1 útvonal található amely áthalad a csúcson:  a [2,1,3] útvonal, amely helyettesíti a [2,3] útvonalat, amelynek kevesebb éle van, de hosszabb (súly szempontjából). A {{Math|1=''k'' = 2}} esetén az {1,2} csúcsokon átmenő utak találhatók. A piros és a kék négyzet megmutatja, hogy a [4,2,1,3] út, hogy állt össze a korábbi iterációkban felismert két útvonalból a [4,2] és [2,1,3]-ból 2-vel a metszéspontban. A [4,2,3] elérési utat nem vesszük figyelembe, mivel a [2,1,3] a legrövidebb út, amelyet eddig a 2-től 3-ig megfigyeltünk. A {{Math|1=''k'' = 3}} esetén a {1,2,3} csúcsokon átmenő utak találhatók. Végül, {{Math|1=''k'' = 4}} -nél az összes legrövidebb útvonal megtalálható.

A távolság mátrixa minden {{Mvar|k}} iterációnál, a frissített távolságokkal ('''vastag betűvel''' jelölve): 
{| class="wikitable" style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{Math|1=''k'' = 0}}
| colspan="4" |{{Mvar|j}}
|-
!1
!2
!3
!4
|-
| rowspan="4" |{{Mvar|i}}
!1
|0
|&#x221E;
|−2
|&#x221E;
|-
!2
|4
|0
|3
|&#x221E;
|-
!3
|&#x221E;
|&#x221E;
|0
|2
|-
!4
|&#x221E;
|−1
|&#x221E;
|0
|}
{| class="wikitable" style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" | {{Math|1=''k'' = 1}} 
| colspan="4" | {{Mvar|j}} 
|-
! 1 
! 2 
! 3 
! 4 
|-
| rowspan="4" | {{Mvar|i}} 
! 1 
| 0 
| &#x221E; 
| -2 
| &#x221E; 
|-
! 2 
| 4 
| 0 
| '''2''' 
| &#x221E; 
|-
! 3 
| &#x221E; 
| &#x221E; 
| 0 
| 2 
|-
! 4 
| &#x221E; 
| -1 
| &#x221E; 
| 0 
|}
{| class="wikitable" style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" | {{Math|1=''k'' = 2}} 
| colspan="4" | {{Mvar|j}} 
|-
! 1 
! 2 
! 3 
! 4 
|-
| rowspan="4" | {{Mvar|i}} 
! 1 
| 0 
| &#x221E; 
| -2 
| &#x221E; 
|-
! 2 
| 4 
| 0 
| 2 
| &#x221E; 
|-
! 3 
| &#x221E; 
| &#x221E; 
| 0 
| 2 
|-
! 4 
| '''3''' 
| -1 
| '''1''' 
| 0 
|}
{| class="wikitable" style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" | {{Math|1=''k'' = 3}} 
| colspan="4" | {{Mvar|j}} 
|-
! 1 
! 2 
! 3 
! 4 
|-
| rowspan="4" | {{Mvar|i}} 
! 1 
| 0 
| &#x221E; 
| -2 
| '''0''' 
|-
! 2 
| 4 
| 0 
| 2 
| '''4''' 
|-
! 3 
| &#x221E; 
| &#x221E; 
| 0 
| 2 
|-
! 4 
| 3 
| -1 
| 1 
| 0 
|}
{| class="wikitable" style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" | {{Math|1=''k'' = 4}} 
| colspan="4" | {{Mvar|j}} 
|-
! 1 
! 2 
! 3 
! 4 
|-
| rowspan="4" | {{Mvar|i}} 
! 1 
| 0 
| '''-1''' 
| -2 
| 0 
|-
! 2 
| 4 
| 0 
| 2 
| 4 
|-
! 3 
| '''5''' 
| '''1''' 
| 0 
| 2 
|-
! 4 
| 3 
| -1 
| 1 
| 0 
|}
{{clear}}

== Viselkedés negatív körökkel ==
A gráfelméletben értelmezett negatív kör egy olyan kör, ahol az élek összege negatív értékhez vezet. Legrövidebb út nem fellelhető egyetlen <math>i</math>, <math>j</math> csúcspár között sem, amelyek egy negatív kör részét képezik, mert az út hossza <math>i</math>-től <math>j</math>-ig tetszőlegesen kicsi (negatív). Numerikusan értelmezhető kimeneti értékhez a  Floyd – Warshall algoritmus feltételezi, hogy nincs negatív kör. Mindazonáltal, ha vannak negatív körök, a Floyd – Warshall algoritmus felhasználható arra, hogy felismerje ezeket. Az intuíció a következő:

* A Floyd–Warshall algoritmus iteratív módon felülvizsgálja az út hosszát az összes csúcspár között <math>(i,j)</math>, beleértve azon eseteket  ahol <math>i=j</math> ; 
* Az út hossza <math>(i,i)</math> kezdetben nulla; 
* Egy adott út <math>[i,k,\ldots,i]</math> csak javulhat, ha a hossza kisebb mint nulla, vagyis negatív kört jelöl; 
* Az algoritmus után <math>(i,i)</math> negatív lesz, ha létezik negatív hosszúságú útvonal az <math>i</math> és <math>i</math> között.

Ennélfogva a negatív [[Kör (gráfelmélet)|körök]], Floyd – Warshall algoritmussal történő felismeréséhez meg kell vizsgálni az út mátrix átlóját, a vizsgálat során negatív szám jelenléte jelzi, hogy a grafikon legalább egy negatív kört tartalmaz.<ref>{{Cite web |first=Dorit |author=Hochbaum |authorlink=Dorit S. Hochbaum |url=http://www.ieor.berkeley.edu/~hochbaum/files/ieor266-2014.pdf |title=Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths |work=Lecture Notes for IEOR 266: Graph Algorithms and Network Flows |date=2014 |format=[[PDF]] |publisher=Department of Industrial Engineering and Operations Research, [[University of California, Berkeley]] |accessdate=2020-06-11 |archiveurl=https://web.archive.org/web/20161020144626/http://www.ieor.berkeley.edu/~hochbaum/files/ieor266-2014.pdf |archivedate=2016-10-20 }}</ref> A numerikus problémák elkerülése érdekében ellenőrizni kell, hogy vannak-e negatív számok az útvonal mátrixának átlójában az algoritmus belső ciklusán belül.<ref>
{{Cite journal|title=The Floyd–Warshall algorithm on graphs with negative cycles|author=Stefan Hougardy|journal=Information Processing Letters|volume=110|date=April 2010|pages=279–281|doi=10.1016/j.ipl.2010.02.001}}</ref> Nyilvánvalóan egy irányítatlan gráfban a negatív él negatív kört (azaz zárt bejárást) hoz létre az érintett csúcsokkal. Figyelembe véve a [[Floyd–Warshall algoritmus#Pelda|fenti]] példa gráfjának minden éle irányítatlan, pl. a 4 - 2 - 4 csúcsszekvencia egy kör, amelynek súlya −2.

== Útvonal helyreállítása ==
A Floyd–Warshall algoritmus általában a csúcspárok közötti útvonalakat adja meg. Azonban egyszerű módosításokkal lehetséges olyan eljárást készíteni ami helyreállítja az útvonalat bármely két végpont csúcsa között. Van rá lehetőség, hogy eltároljuk a tényleges útvonalat az egyik csúcstól egy adott másik csúcshoz, de ez nem szükséges, sőt tárhelyfelhasználás (memória) szempontjából eléggé költséges. Ehelyett a [[Legrövidebb út probléma|legrövidebb út]]<nowiki/>vonal kiszámítható minden egyes <math>\Theta(|E|)</math> csomópontoknak, <math>\Theta(|V|)</math> idő alatti tárhely felhasználásával amely az egyes fák tárolására szolgáló memória, amely lehetővé teszi számunkra, hogy hatékonyan rekonstruáljunk egy utat bármely két csatlakoztatott csúcsból.

=== Pszeudókód <ref>https://books.goalkicker.com/AlgorithmsBook/</ref>===
 Legyen az ún. 'tavolsag' <math>|V| \times |V|</math> minimális távolságok tömbje, inicializálva <math>\infty</math>-ig(végtelen)
 Legyen a 'kovetkezo' a <math>|V| \times |V|</math> csúcsindexek tömbje amely '''null''' értékkel inicializálódik.
 
 '''procedure''' ''FloydWarshallUtvonalHelyreallitassal''() '''is'''
     '''for each''' el (u, v) '''do'''
         tavolsag[u][v] &#x2190; w(u, v)  ''// Az adott él súlya (u, v)''
         kovetkezo[u][v] &#x2190; v
     '''for each''' csucs v '''do'''
         tavolsag[''v''][''v''] &#x2190; 0
         kovetkezo[v][v] &#x2190; v
     '''for''' k '''from''' 1 '''to''' |V| '''do''' ''// általános Floyd-Warshall implementáció''
         '''for''' i '''from''' 1 '''to''' |V|
             '''for''' j '''from''' 1 '''to''' |V|
                 '''if''' tavolsag[i][j] > tavolsag[i][k] + tavolsag[k][j] '''then'''
                     tavolsag[i][j] &#x2190; tavolsag[i][k] + tavolsagg[k][j]
                     kovetkezo[i][j] &#x2190; kovetkezo[i][k]

 '''procedure''' Utvonal(u, v)
     '''if''' tavolsag[u][v] = null '''then'''
         '''return''' []
     ut = [u]
     '''while''' ''u'' ≠ ''v''
         u &#x2190; kovetkezo[u][v]
         ut.append(u)
     '''return''' ut

== Elemzés ==
Legyen <math>n</math> a <math>|V|</math>, azaz a csúcsok száma . Ahhoz, hogy megtaláljuk az összes <math>n^2</math> értéket a <math>\mathrm{legrovidebbUtvonal}(i ,j ,k )</math>-hoz tartozóan (minden <math>i</math> és <math>j</math>) azokból ahol a <math>\mathrm{legrovidebbUtvonal}(i ,j ,k-1)</math>, <math>2n^2</math> számú műveletet igényel. Mivel úgy kezdünk, hogy a <math>\mathrm{legrovidebbUtvonal}(i, j, 0) = elKoltseg(i, j)</math> és kiszámítjuk az adott <math>n</math> mátrixok <math>\mathrm{legrovidebbUtvonal}(i ,j , 1)</math>, <math>\mathrm{legrovidebbUtvonal}(i ,j , 2)</math>, <math>\ldots</math>, <math>\mathrm{legrovidebbUtvonal}(i ,j , N)</math>, összes használt műveletnek a számát, ami:
<math>n \cdot 2n^2 = 2n^3</math>. Ezért az algoritmus [[számítási bonyolultságelmélet|bonyolultsága]]: [[O jelölés|<math>\Theta(n^3)</math>]].

== Alkalmazások és általánosítások ==
A Floyd – Warshall algoritmus felhasználható többek között a következő problémák megoldására:

* A legrövidebb útvonal számítására irányított gráfokban (Floyd algoritmusa). 
* Irányított gráfok tranzitív lezárására (Warshall algoritmus). Eredeti megfogalmazásában a Warshall algoritmusban a gráf nem súlyozott, és egy logikai szomszédsági mátrix képviseli. Az összeadási műveletet helyettesíti a [[Konjunkció|logikai összekapcsolás]] (ÉS), a minimális művelet pedig [[Diszjunkció|logikus diszjunció]] (VAGY). 
* [[Végtelen automata|Véges automata]] által elfogadott [[Reguláris nyelv|szabályos nyelvet]] jelölő [[reguláris kifejezés]] keresése ( [[Kleene algoritmusa]], amely egy szorosan kapcsolódó általánosítása a Floyd – Warshall algoritmusnak) <ref>{{Citation|title=Handbook of Graph Theory|series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2003|page=65|url=https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204}}.</ref> 
* [[Valós számok|Valós]] [[Mátrix (matematika)|mátrixok]] [[Invertálható mátrix|inverziója]] ( [[Gauss-elimináció|Gauss – Jordan algoritmus]] ) <ref>{{Cite journal|title=Algebraic Structures for Transitive Closure|first=Rafael|author=Penaloza}}</ref> 
* Optimális útvonal választás. Ebben az alkalmazásban az érdekesség megtalálni az utat a két csúcs között, maximális áramlással. Ahelyett, hogy a minimumokat vennénk mint a fentebb látható pszeudókódban is, inkább a maximumokat vesszük. Az élek súlya rögzített kényszert reprezentál az áramlásban. Az útvonal súlya ún. szűkületet ábrázol; így a fenti összeadás műveletet a minimális művelet váltja fel. 
* A Pathfinder (útvonal-kereső) hálózatok gyors kiszámítása. 
* [[A legszélesebb út probléma|Legszélesebb útvonalak / Maximális sávszélesség-útvonalak]] 
* A különbséghez kötött mátrixok (DBM) kanonikus formájának kiszámítása 
* A gráfok közötti hasonlóság kiszámítása

== Megvalósítások ==
Az algoritmus megvalósításai megannyi [[programozási nyelv]]en rendelkezésre állnak.

* [[C++]] esetén [http://www.boost.org/libs/graph/doc/ boost::graph] könyvtár
* [[C Sharp|C#]] esetén a [https://web.archive.org/web/20100317031339/http://www.codeplex.com/quickgraph QuickGraph]
* Továbbá [[C Sharp|C#]] esetén a [https://www.nuget.org/packages/QuickGraphPCL/3.6.61114.2 QuickGraphPCL] (Hasonló a QuickGraph-hoz azonban jobb kompatibilitással rendelkezik azon projekteknél amik PCL-t használnak.)
* [[Java (programozási nyelv)|Java]] esetén az [http://commons.apache.org/sandbox/commons-graph/ Apache Commons Graph] könyvtár
* [[JavaScript]] esetén a Cytoscape könyvtár
* [[MATLAB]] esetén a [http://www.mathworks.com/matlabcentral/fileexchange/10922 Matlab_bgl] csomag
* [[Perl (programozási nyelv)|Perl]] esetén [https://metacpan.org/module/Graph Graph] modul
* [[Python (programozási nyelv)|Python]] esetén a SciPy könyvtárban (a [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.floyd_warshall.html#scipy.sparse.csgraph.floyd_warshall scipy.sparse.csgraph] modul) vagy NetworkX könyvtár
* [[R (programozási nyelv)|R]] esetén a [https://cran.r-project.org/web/packages/e1071/index.html e1071] és [https://cran.r-project.org/web/packages/Rfast/index.html Rfast]

== Összehasonlítás más legrövidebb út alapú algoritmusokkal ==
A Floyd – Warshall algoritmus jó választás az útvonal kiszámításához az összes csúcspár között [[Sűrű gráf|sűrű grafikonokban]], amelyekben a csúcsok többségét vagy az összeset élek kötik össze. A nem negatív élsúlyú ritka gráfok esetében jobb választás, ha [[Dijkstra-algoritmus|Dijkstra algoritmusát]] használjuk minden lehetséges kezdőpontból, mivel az ismételt Dijkstra futási ideje ( <math>O(|E||V|+|V|^2\log|V|)</math> (Fibonacci halom) jobb, mint  <math>O(|V|^3)</math> a Floyd – Warshall algoritmus futási ideje, amikor <math>|E|</math> jelentősen kisebb, mint <math>|V|^2</math>. A negatív élekkel rendelkező, de negatív körök nélküli ritka gráfoknál Johnson algoritmusa használható, ugyanolyan futási idővel, mint az ismételt Dijkstra megközelítésnél.

Vannak ismert algoritmusok, amelyek gyors mátrixszorzást használnak az összes pár legrövidebb útjának kiszámításához sűrű grafikonokban, ám ezek általában további kikötéseket fogalmaznak meg az élsúlyokhoz (például előírják, hogy kis egész számok legyenek).<ref>{{Citation|last=Zwick|first=Uri|authorlink=Uri Zwick|date=May 2002|doi=10.1145/567112.567114|issue=3|journal=[[Journal of the ACM]]|pages=289–317|title=All pairs shortest paths using bridging sets and rectangular matrix multiplication|volume=49}}.</ref><ref>{{Citation|last=Chan|first=Timothy M.|authorlink=Timothy M. Chan|date=January 2010|doi=10.1137/08071990x|issue=5|journal=[[SIAM Journal on Computing]]|pages=2075–2089|title=More algorithms for all-pairs shortest paths in weighted graphs|volume=39}}.</ref> Ezen túlmenően a futási idejükben fellelhető állandó tényezők miatt csak a nagyon nagy grafikonok esetében lennének gyorsabbak mint a Floyd – Warshall algoritmus.

== Irodalom ==
{{Reflist}}

== Külső linkek ==

* [http://www.pms.informatik.uni-muenchen.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization A Floyd – Warshall algoritmus interaktív animációja] 
* [https://www-m9.ma.tum.de/graph-algorithms/spp-floyd-warshall/index_en.html A Floyd – Warshall algoritmus interaktív animációja (Müncheni Műszaki Egyetem)] {{Wayback|url=https://www-m9.ma.tum.de/graph-algorithms/spp-floyd-warshall/index_en.html |date=20191030184624 }}

== Fordítás ==
{{fordítás|en|Floyd–Warshall algorithm}}

[[Kategória:Gráfalgoritmusok]]