Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

6.6. Legrövidebb utak minden csúcspárra

6.6. Legrövidebb utak minden csúcspárra

Ebben a fejezetben célunk egy gráf valamennyi rendezett csúcspárjára a két csúcs közti legrövidebb út megkeresése. Ha például egy autóstérképhez elkészítjük a városok egymástól mért távolságainak táblázatát, éppen ezt a feladatot oldjuk meg. Csakúgy, mint korábban egy súlyozott irányított gráfot jelöl, amelynek élhalmazán egy valós értékű súlyfüggvény van megadva. A gráf minden csúcspárjára keressük az -ból -be vezető legrövidebb (legkisebb súlyú) utat, ahol egy út súlya az úthoz tartozó élek súlyának az összege. Az eredményt általában táblázatos formában keressük; a táblázat -hoz tartozó sorában és -hez tartozó oszlopában álló elem az -ból -be vezető legrövidebb út hossza.

A csúcspárok közti legrövidebb utakat természetesen megkereshetjük úgy, hogy az előző fejezetben látott valamelyik egy kezdőcsúcsból kiinduló legrövidebb utakat kereső algoritmust egyenként végrehajtunk a lehetséges különböző gyökércsúcsot választva. Ha a távolságok nemnegatívak, Dijkstra algoritmusát alkalmazhatjuk.

Ha negatív élsúlyokat is megengedünk a gráfban, Dijkstra algortmusa nem alkalmazható, helyette a lassabb Bellman-Ford-algoritmust kell minden csúcsra egyszer végrehajtanunk. Célunk tehát, hogy a negatív élsúlyok esetére hatékonyabb algoritmusokat adjunk. Eközben megismerjük az összes csúcspár közti legrövidebb út probléma és a mátrixszorzás kapcsolatát is.

Az egy csúcsból kiinduló legrövidebb utakat megadó algoritmusok általában a gráf éllistás megadását igénylik. A bemenő adat tehát egy -es mátrix lesz. A mátrix egy csúcsú irányított gráf élsúlyait tartalmazza: , ahol

A gráfban megengedünk negatív súlyú éleket, azonban egyelőre feltesszük, hogy negatív összsúlyú körök nincsenek.

A fejezetbeli algoritmus kimenete az összes párra adott legrövidebb úthosszakat tartalmazó táblázat egy D -es mátrix lesz. A mátrix eleme az csúcsból a csúcsba vezető legrövidebb út súlyát tartalmazza. A végeredményként kapott értékek tehát megegyeznek a -vel, az csúcsból a csúcsba vezető legrövidebb út súlyával.

Csak akkor mondhatjuk, hogy a kitűzött feladatot megoldottuk, ha a legrövidebb utak súlya mellett magukat az utakat is meg tudjuk adni. E célból egy megelőzési mátrixot is meg kell adnunk, amelyben , ha vagy ha nem vezet és között út; ellenkező esetben a -t megelőző csúcs az egyik -ből -be vezető legrövidebb úton.

Mielőtt az algoritmust ismertetnénk, állapodjunk meg néhány, szomszédsági mátrixokkal kapcsolatos, jelölésben. Először is a gráfnak általában csúcsa lesz, azaz . Másodszor a mátrixokat nagybetűvel, egyes elemeiket pedig alulindexelt kisbetűvel fogjuk jelölni, tehát például és elemei lesznek. Bizonyos esetekben iterációk jelölésére a mátrixokat zárójelezett felsőindexszel látjuk el, úgy mint . Végül egy adott A -es mátrix esetén sorok-száma[A] tartalmazza értékét.

6.6.1. A Floyd-Warshall-algoritmus

A következőkben dinamikus programozási feladatként értelmezzük a legrövidebb utak keresését. Egy irányított gráfon a keletkező ún. Floyd-Warshall-algoritmus futási ideje . A bemenő gráfban megengedünk negatív élsúlyokat, negatív összsúlyú köröket azonban nem.

A legrövidebb utak szerkezete

Dinamikus programozásunk a legrövidebb utak ,,belső” csúcsait tekinti, ahol egy egyszerű út belső csúcsa minden -től és -től különböző csúcsa, azaz a halmaz minden eleme.

A szerkezet jellemzése a következő észrevételen alapul. Legyen a gráf csúcshalmaza , és tekintsük valamely -ra az részhalmazt. Legyen a legrövidebb -ből -be vezető olyan út, melynek belső csúcsait az részhalmazból választhatjuk. (A út egyszerű, hiszen nem tartalmaz negatív összsúlyú köröket.) A Floyd-Warshall-algoritmus a út és az olyan legrövidebb utak kapcsolatát alkalmazza, melynek belső csúcsait az részhalmazból választjuk. E kapcsolat két esetre osztható attól függően, hogy belső csúcsa-e -nek vagy sem:

  • Ha a útnak nem belső csúcsa, akkor a út minden belső csúcsa az halmaz eleme. Így a legrövidebb -ből -be vezető és belső csúcsként csak az halmaz elemeit használó út szintén legrövidebb út lesz, ha a belső csúcsok az halmazból kerülhetnek ki.

  • Ha belső csúcs a úton, akkor felbontjuk a utat két útra. A egy olyan legrövidebb út és között, melynek belső csúcsai az halmaz elemei. Sőt nem is lehet út belső csúcsa, így egyben olyan legrövidebb út is, melynek belső csúcsai -beliek. Hasonlóképpen egy legrövidebb, belső csúcsként csak -et használó -ból -be vezető út.

Az összes csúcspár közti legrövidebb utak rekurzív megadása

A fenti megfigyelés alapján egy rekurzióval adhatunk egyre javuló becsléseket a legrövidebb utak súlyára. Legyen a legrövidebb olyan -ből -be vezető út hossza, melynek minden belső csúcsa az halmaz eleme. A érték esetén egy olyan -ből -be vezető útnak, melyen a belső csúcsok sorszáma legfeljebb 0 lehet, egyáltalán nem lehet belső csúcsa. Egy ilyen útnak tehát legfeljebb egyetlen éle lehet és így . A további értékeket a következő rekurzió szolgáltatja:

A végeredményt a mátrix tartalmazza, hiszen az egyes legrövidebb utak belső csúcsai a halmaz elemei, és így minden esetén.

Az úthosszak kiszámítása alulról felfelé haladva

A 6.2 rekurzió segítségével a értékeket alulról felfelé, értéke szerinti növekvő sorrendben számíthatjuk. Az algoritmus bemenő adatai a 6.1 egyenlőség által definiált -es mátrix lesz, eredményül pedig a legrövidebb úthosszak mátrixát adja.

A Floyd-Warshall-algoritmus futási idejét a 3-6. sorok háromszorosan egymásba ágyazott FOR ciklusa határozza meg. A 6. sor minden egyes alkalommal időben végrehajtható, így a teljes futási idő . A megadott programkód tömör és csak egyszerű adatszerkezeteket igényel. A -jelölésbeli állandó tehát kicsi, és a Floyd-Warshall-algoritmus még közepesen nagy méretű gráfok esetén is hatékony.

A és mátrixok, ha a Floyd-Warshall-algoritmust az ábrán látható gráfon futtatjuk.

A legrövidebb utak megadása

A Floyd-Warshall-algoritmusban több módszer is kínálkozik arra, hogy a legrövidebb utak éleit is megkapjuk. Megtehető, hogy a legrövidebb úthosszak mátrixának ismeretében idő alatt megkonstruáljuk a { } megelőzési mátrixot. A { } megelőzési mátrix ismeretében pedig a Minden-párhoz-utat-nyomtat eljárás megadja a kívánt két csúcs közti legrövidebb út éleit.

A megelőzési mátrixot számíthajuk a Floyd-Warshall-algoritmus menetében a mátrixokkal egyidejűleg is. Pontosabban mátrixok egy sorozatát számíthatunk, melyre . E sorozatban -t úgy definiáljuk, mint egy olyan legrövidebb -ből -be vezető úton a -t megelőző csúcsot, melynek belső csúcsai a halmaz elemei.

Megadjuk a értékeit definiáló rekurziót. (A mátrixok számítása az ábra példájában követhető.) Ha , akkor -től -ig tartó úton nincs közbülső csúcs és így

A esetben pedig egy úton a -t megelőző csúcsnak választható ugyanaz a csúcs, amely -t egy legrövidebb -ból induló és belső csúcsként csak az halmaz elemeit használó úton előzi meg. Ha pedig a legrövidebb -ből -be vezető és az halmaz elemeit használó út -t nem tartalmazza, akkor a -t megelőző csúcs megegyezik a érték esetén választott megelőző csúccsal. Tehát mellett a rekurzív egyenlet