Floyd–Warshall-algoritmus

	Floyd–Warshall-algoritmus
Kategória	Legrövidebb út probléma (súlyozott gráfok esetében)
Adatstruktúra	Gráf
Legrosszabb időbonyolultság
Legjobb időbonyolultság
Átlagos idő bonyolultság
Legrosszabb tár bonyolultság

A 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 útvonalakat egy pozitív vagy negatív élsúlyú súlyozott gráfban . (de negatív körök nélkül).^[1]^[2] 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ást, vagy (a Schulze-módszerrel összefüggésben) a legszélesebb útvonalakat az összes csúcspár között egy súlyozott grafikonon.

Előzmények és elnevezések szerkesztés

A Floyd–Warshall-algoritmus a dinamikus programozás egy jól ismert példája, melyet Robert Floyd publikált 1962-ben.^[3] Alapvetően megegyezik azon algoritmusokkal, melyeket korábban Bernard Roy 1959-ben kiadott^[4] és továbbá Stephen Warshall 1962-ben ^[5] 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 automata konvertálása szabályos kifejezésekké.^[6] 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.^[7]

Algoritmus szerkesztés

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 $\Theta (|V|^{3})$ összehasonlítással egy gráfban, bár lehet, hogy akár $\Omega (|V|^{2})$ é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 $G$ grafikont, $V$ csúcsokkal 1-től $N$ -ig számozva. Továbbá egy függvényt az ún. $\mathrm {legrovidebbUtvonal} (i,j,k)$ amely visszatér a legrövidebb útvonallal $i$ és $j$ között adott csúcsok használatával: $\{1,2,\ldots ,k\}$ 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 $i$ -től minden $j$ -ig bármelyik csúcs használatával: $\{1,2,\ldots ,N\}$ .

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

(1) egy útvonal, amely nem megy át

k

-n (amely csak az adott csúcsokat használja:

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

)

vagy

(2) egy útvonal, amely végigmegy

k

-n (

i

-től

k

-ig és aztán

k

-tól

j

-ig, mindkét esetben az adott közbenső csúcsokat használva:

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

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

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

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

a rekurzív eset a következő:

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

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

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

.

Ez a képlet a Floyd–Warshall algoritmus szive. Az algoritmus futása során először kiszámolja a $\mathrm {legrovidebbUtvonal} (i,j,k)$ alapján az $(i,j)$ pároknak a $k=1$ , majd $k=2$ és így tovább. Ez a folyamat addig folytatódik, amíg $k=N$ , és megtaláltuk a legrövidebb utat mindegyik $(i,j)$ 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] ← w(u, v)  // Az adott él súlya (u, v)
for each csucs v do
    tavolsag[v][v] ← 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] ← tavolsag[i][k] + tavolsag[k][j]
            end if

Példa szerkesztés

A fenti algoritmust az alább látható bal oldali grafikonon láthatjuk:

A külső hurok első rekurziója előtt, a fenti $k = 0$ jelöléssel láthatjuk, az egyetlen ismert útvonalat amely megfelel a grafikon egyes széleinek. $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 $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 $k = 3$ esetén a {1,2,3} csúcsokon átmenő utak találhatók. Végül, $k = 4$ -nél az összes legrövidebb útvonal megtalálható.

A távolság mátrixa minden $k$ iterációnál, a frissített távolságokkal (vastag betűvel jelölve):


$k = 0$		1	2	3	4
$k = 0$		$j$
$i$	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


$k = 1$		1	2	3	4
$k = 1$		$j$
$i$	1	0	∞	-2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	-1	∞	0


$k = 2$		1	2	3	4
$k = 2$		$j$
$i$	1	0	∞	-2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	-1	1	0


$k = 3$		1	2	3	4
$k = 3$		$j$
$i$	1	0	∞	-2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	-1	1	0


$k = 4$		1	2	3	4
$k = 4$		$j$
$i$	1	0	-1	-2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	-1	1	0

Viselkedés negatív körökkel szerkesztés

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 $i$ , $j$ csúcspár között sem, amelyek egy negatív kör részét képezik, mert az út hossza $i$ -től $j$ -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 $(i,j)$ , beleértve azon eseteket ahol $i=j$ ;
Az út hossza $(i,i)$ kezdetben nulla;
Egy adott út $[i,k,\ldots ,i]$ csak javulhat, ha a hossza kisebb mint nulla, vagyis negatív kört jelöl;
Az algoritmus után $(i,i)$ negatív lesz, ha létezik negatív hosszúságú útvonal az $i$ és $i$ között.

Ennélfogva a negatív 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.^[8] 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.^[9] 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 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 szerkesztés

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 útvonal kiszámítható minden egyes $\Theta (|E|)$ csomópontoknak, $\Theta (|V|)$ 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 ^[10] szerkesztés

Legyen az ún. 'tavolsag'  $|V|\times |V|$  minimális távolságok tömbje, inicializálva  $\infty$ -ig(végtelen)
Legyen a 'kovetkezo' a  $|V|\times |V|$  csúcsindexek tömbje amely null értékkel inicializálódik.

procedure FloydWarshallUtvonalHelyreallitassal() is
    for each el (u, v) do
        tavolsag[u][v] ← w(u, v)  // Az adott él súlya (u, v)
        kovetkezo[u][v] ← v
    for each csucs v do
        tavolsag[v][v] ← 0
        kovetkezo[v][v] ← 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] ← tavolsag[i][k] + tavolsagg[k][j]
                    kovetkezo[i][j] ← kovetkezo[i][k]

procedure Utvonal(u, v)
    if tavolsag[u][v] = null then
        return []
    ut = [u]
    while u ≠ v
        u ← kovetkezo[u][v]
        ut.append(u)
    return ut

Elemzés szerkesztés

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

Alkalmazások és általánosítások szerkesztés

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 logikai összekapcsolás (ÉS), a minimális művelet pedig logikus diszjunció (VAGY).
Véges automata által elfogadott 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) ^[11]
Valós mátrixok inverziója ( Gauss – Jordan algoritmus ) ^[12]
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.
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 szerkesztés

Az algoritmus megvalósításai megannyi programozási nyelven rendelkezésre állnak.

C++ esetén boost::graph könyvtár
C# esetén a QuickGraph
Továbbá C# esetén a QuickGraphPCL (Hasonló a QuickGraph-hoz azonban jobb kompatibilitással rendelkezik azon projekteknél amik PCL-t használnak.)
Java esetén az Apache Commons Graph könyvtár
JavaScript esetén a Cytoscape könyvtár
MATLAB esetén a Matlab_bgl csomag
Perl esetén Graph modul
Python esetén a SciPy könyvtárban (a scipy.sparse.csgraph modul) vagy NetworkX könyvtár
R esetén a e1071 és Rfast

Összehasonlítás más legrövidebb út alapú algoritmusokkal szerkesztés

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ű 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át használjuk minden lehetséges kezdőpontból, mivel az ismételt Dijkstra futási ideje ( $O(|E||V|+|V|^{2}\log |V|)$ (Fibonacci halom) jobb, mint $O(|V|^{3})$ a Floyd – Warshall algoritmus futási ideje, amikor $|E|$ jelentősen kisebb, mint $|V|^{2}$ . 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).^[13]^[14] 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 szerkesztés

↑ 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.
↑ Kenneth H. Rosen. Discrete Mathematics and Its Applications, 5th Edition. Addison Wesley (2003). ISBN 978-0-07-119881-3
↑ Floyd (1962. június 1.). „Algorithm 97: Shortest Path”. Communications of the ACM 5 (6), 345. o. DOI:10.1145/367766.368168.
↑ Roy (1959). „Transitivité et connexité.” (french nyelven). C. R. Acad. Sci. Paris 249, 216–218. o.
↑ Warshall (1962. január 1.). „A theorem on Boolean matrices”. Journal of the ACM 9 (1), 11–12. o. DOI:10.1145/321105.321107.
↑ Kleene, S. C..szerk.: C. E. Shannon and J. McCarthy: Representation of events in nerve nets and finite automata, Automata Studies. Princeton University Press, 3–42. o. (1956)
↑ Ingerman (1962. november 1.). „Algorithm 141: Path Matrix”. Communications of the ACM 5, 556. o. DOI:10.1145/368996.369016.
↑ Hochbaum: Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths (PDF). Lecture Notes for IEOR 266: Graph Algorithms and Network Flows. Department of Industrial Engineering and Operations Research, University of California, Berkeley, 2014 [2016. október 20-i dátummal az eredetiből archiválva]. (Hozzáférés: 2020. június 11.)
↑ Stefan Hougardy (2010. április 1.). „The Floyd–Warshall algorithm on graphs with negative cycles”. Information Processing Letters 110, 279–281. o. DOI:10.1016/j.ipl.2010.02.001.
↑ https://books.goalkicker.com/AlgorithmsBook/
↑ Gross, Jonathan L. & Yellen, Jay (2003), Handbook of Graph Theory, Discrete Mathematics and Its Applications, CRC Press, p. 65, ISBN 9780203490204, <https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65>.
↑ Penaloza. „Algebraic Structures for Transitive Closure”.
↑ Zwick, Uri (May 2002), "All pairs shortest paths using bridging sets and rectangular matrix multiplication", Journal of the ACM 49 (3): 289–317, DOI 10.1145/567112.567114.
↑ Chan, Timothy M. (January 2010), "More algorithms for all-pairs shortest paths in weighted graphs", SIAM Journal on Computing 39 (5): 2075–2089, DOI 10.1137/08071990x.

Külső linkek szerkesztés

A Floyd – Warshall algoritmus interaktív animációja
A Floyd – Warshall algoritmus interaktív animációja (Müncheni Műszaki Egyetem) Archiválva 2019. október 30-i dátummal a Wayback Machine-ben

Fordítás szerkesztés

Ez a szócikk részben vagy egészben a Floyd–Warshall algorithm című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

[1] 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.

[2] Kenneth H. Rosen. Discrete Mathematics and Its Applications, 5th Edition. Addison Wesley (2003). ISBN 978-0-07-119881-3

[3] Floyd (1962. június 1.). „Algorithm 97: Shortest Path”. Communications of the ACM 5 (6), 345. o. DOI:10.1145/367766.368168.

[4] Roy (1959). „Transitivité et connexité.” (french nyelven). C. R. Acad. Sci. Paris 249, 216–218. o.

[5] Warshall (1962. január 1.). „A theorem on Boolean matrices”. Journal of the ACM 9 (1), 11–12. o. DOI:10.1145/321105.321107.

[6] Kleene, S. C..szerk.: C. E. Shannon and J. McCarthy: Representation of events in nerve nets and finite automata, Automata Studies. Princeton University Press, 3–42. o. (1956)

[7] Ingerman (1962. november 1.). „Algorithm 141: Path Matrix”. Communications of the ACM 5, 556. o. DOI:10.1145/368996.369016.

[8] Hochbaum: Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths (PDF). Lecture Notes for IEOR 266: Graph Algorithms and Network Flows. Department of Industrial Engineering and Operations Research, University of California, Berkeley, 2014 [2016. október 20-i dátummal az eredetiből archiválva]. (Hozzáférés: 2020. június 11.)

[9] Stefan Hougardy (2010. április 1.). „The Floyd–Warshall algorithm on graphs with negative cycles”. Information Processing Letters 110, 279–281. o. DOI:10.1016/j.ipl.2010.02.001.

[10] ttps://books.goalkicker.com/AlgorithmsBook/

[11] Gross, Jonathan L. & Yellen, Jay (2003), Handbook of Graph Theory, Discrete Mathematics and Its Applications, CRC Press, p. 65, ISBN 9780203490204, <https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65>.

[12] Penaloza. „Algebraic Structures for Transitive Closure”.

[13] Zwick, Uri (May 2002), "All pairs shortest paths using bridging sets and rectangular matrix multiplication", Journal of the ACM 49 (3): 289–317, DOI 10.1145/567112.567114.

[14] Chan, Timothy M. (January 2010), "More algorithms for all-pairs shortest paths in weighted graphs", SIAM Journal on Computing 39 (5): 2075–2089, DOI 10.1137/08071990x.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Floyd–Warshall-algoritmus

Kategória	Legrövidebb út probléma (súlyozott gráfok esetében)
Adatstruktúra	Gráf
Legrosszabb időbonyolultság	$\Theta (\|V\|^{3})$
Legjobb időbonyolultság	$\Theta (\|V\|^{3})$
Átlagos idő bonyolultság	$\Theta (\|V\|^{3})$
Legrosszabb tár bonyolultság	$\Theta (\|V\|^{2})$