Johnson algoritmusa

Johnson algoritmus
Kategória	Legrövidebb út probléma (súlyozott gráfok esetében)
Adatstruktúra	Gráf
Legrosszabb időbonyolultság	${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$

Johnson algoritmusa lehetővé teszi a legrövidebb utak megtalálását az összes csúcspár között egy súlyozott élekkel rendelkező irányított gráfban . Lehetőséget ad arra, hogy egyes élek súlya negatív szám legyen, de nem lehet negatív súlyozott kör. A Bellman – Ford algoritmus segítségével működik egy olyan bemeneti gráf transzformációjának kiszámításához, amely eltávolítja az összes negatív súlyt, lehetővé téve Dijkstra algoritmusának használatát a transzformált gráfon.^[1][2] Donald B. Johnson után nevezték el az algoritmust, aki 1977-ben publikálta a technikát.^[3]

Hasonló újra-súlyozási technikát alkalmaznak Suurballe algoritmusában is, hogy két nem negatív élsúlyú grafikonon két minimális teljes hosszúságú és diszjunkt utat keressen ugyanazon két csúcs között.^[4]

Algoritmus leírása

Johnson algoritmusa a következő lépésekből áll.^[1][2]

1. Először egy új q csúcsot adunk a gráfhoz, amelyet nulla súlyú élek kötnek össze a többi csomóponttal.
2. Másodszor, a Bellman – Ford algoritmust használjuk, az új q csúcsról kezdve, hogy minden v csúcsra megkeressük a q és v útvonal minimális h(v) súlyát. Ha ez a lépés negatív kört észlel, az algoritmus leáll.
3. Ezután az eredeti gráf éleit újrasúlyozzuk a Bellman – Ford algoritmus által kiszámított értékek felhasználásával: vegyük az u-tól v-ig tartó élt, aminek hosszúsága w(u, v), megkapja az új hosszúságot ami w(u, v) + h(u) – h(v).
4. Végül q-t eltávolítjuk, és a Dijkstra algoritmust használunk, hogy megtaláljuk a legrövidebb utat minden s csomóponttól minden más csúcshoz a újrasúlyozott gráfon. Ezután kiszámolódik a távolság az eredeti gráfon minden D(u, v)-hez úgy, hogy h(v) − h(u)-t adunk a Dijkstra algoritmusa által visszaadott távolság értékekhez.

Példa

Johnson algoritmusának első három szakaszát a jobb oldali ábra szemlélteti.

A kép bal oldalán látható gráfnak két negatív éle van, de nincs negatív köre. A középső gráfon látható az új q csúcs, a Bellman – Ford algoritmus által kiszámított legrövidebb útvonal fája, a q kezdő csúccsal, és a h(v) érték amely csomópontonként számolódik mégpedig aszerint, hogy mennyi a legrövidebb út távolsága a q-tól az adott csomópontig. Figyelembe kell venni, hogy ezek az értékek nem pozitívak, mivel a q-nak nulla hosszúságú éle van minden egyes csúcsnál, és a legrövidebb út nem lehet hosszabb, mint az él. A jobb oldalon látható az újra súlyozott gráf, amelyet az egyes élsúlyok kicserélésével alakítottak ki (w(u, v) => w(u,v) + h(u) − h(v))..Ezen újra súlyozott gráfban az egyik él súlya sem negatív, de bármely két csomópont közötti legrövidebb útvonal ugyanazon éleket használja, mint az eredeti grafikon két csúcsa közötti legrövidebb út. Az algoritmus úgy fejeződik be, hogy Dijkstra algoritmusát alkalmazzuk az újra súlyozott gráfokon mind a négy kezdő csomópontra.

Helyessége

Az újra súlyozott gráfokon az összes s és t csomópont közötti útvonal azonos h(s) − h(t) értékekkel egészül ki. Az előző állítás a következőkkel bizonyítható: Legyen p egy adott s – t útvonal. A W értéke az újrasúlyozott gráfon az alább látható kifejezés alapján számítható:

${\displaystyle {\bigl (}w(s,p_{1})+h(s)-h(p_{1}){\bigr )}+{\bigl (}w(p_{1},p_{2})+h(p_{1})-h(p_{2}){\bigr )}+...+{\bigl (}w(p_{n},t)+h(p_{n})-h(t){\bigr )}.}$

Minden ${\displaystyle +h(p_{i})}$ megszünteti a ${\displaystyle -h(p_{i})}$-t az előző zárójeles kifejezésben; így a következőre változik a W számításának kifejezése:

${\displaystyle {\bigl (}w(s,p_{1})+w(p_{1},p_{2})+...+w(p_{n},t){\bigr )}+h(s)-h(t)}$

Az zárójelezett kifejezés a p súlya. (az eredeti súlyozás alapján)

Mivel az újbóli súlyozás ugyanazt a súlyt rendeli hozzá minden s – t útvonalhoz, egy út az eredeti súlyozásban akkor számít a legrövidebb útvonalnak, és csak akkor, ha az az újra súlyozás után is a legrövidebb. Az élek súlya ami a legrövidebb útvonalhoz tartozik nulla a q-tól akármelyik csomópontig, ezért a legrövidebb út távolsága a q-tól bármelyik csomópont felé nulla lesz az újra súlyozott gráfon, azonban továbbra is a legrövidebb útnak számít. Ezért nem lehetnek negatív élek: ha az uv él negatív tömegű lesz az újbóli súlyozás után, akkor a q és u közötti nullhosszúság ezzel az éllel egy negatív hosszúságú útvonalat képez q-tól v-ig, ellentmondva annak, hogy az összes csúcs nulla távolságra van q-tól . A negatív élek hiánya biztosítja a Dijkstra algoritmusa által megtekintett útvonalak optimalitását. Az eredeti gráfban szereplő távolságok kiszámíthatók a Dijkstra algoritmusa által kiszámított távolságokból az újra súlyozott gráfon az újra súlyozási átalakítás megfordításával.^[1]

Elemzés

Ennek az algoritmusnak az idő bonyolultsága, a Fibonacci halom felhasználásával és Dijkstra algoritmusának megvalósításában: ${\displaystyle O(|V|^{2}\log |V|+|V||E|)}$ Továbbá ${\displaystyle O(|V||E|)}$ az algoritmus Bellman – Ford szakaszának ideje, és ${\displaystyle O(|V|\log |V|+|E|)}$ idő a ${\displaystyle |V|}$ minden példányára a Dijkstra algoritmusban. Így ha a gráf ritka, az összideje gyorsabb lehet, mint a Floyd – Warshall algoritmus, amely ugyanazt a problémát oldja meg adott idővel: ${\displaystyle O(|V|^{3})}$ .^[1]

Külső linkek

• Boost: Minden pár legrövidebb útvonala

Fordítás

• Ez a szócikk részben vagy egészben a Johnson's 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.

Jegyzetek

1. Cormen, Thomas H.; Leiserson, Charles E. & Rivest, Ronald L. et al. (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.
2. Black, Paul E. (2004), "Johnson's Algorithm", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, <https://xlinux.nist.gov/dads/HTML/johnsonsAlgorithm.html>.
3. Johnson, Donald B. (1977), "Efficient algorithms for shortest paths in sparse networks", Journal of the ACM 24 (1): 1–13, DOI 10.1145/321992.321993.
4. Suurballe, J. W. (1974), "Disjoint paths in a network", Networks 14 (2): 125–145, DOI 10.1002/net.3230040204.