Džonsonov algoritam

Dzonsonov algoritam је način da se pronađu najkraći putevi između svih parova čvorova proređenog usmerenog grafa. On omogućava da neke od tezina ivica budu negativne vrednosti, ali ne i ciklusi negativne-težine. Ona radi koristeći Belman-Fordov algoritam za računanje transformacije ulaznog grafa koja uklanja sve negativne težine omogućavajući da se Dijkstra algoritam koristi na transformisanom grafu. Dobio je naziv po Donaldu B. Džonsonu, koji je prvi objavio ovu tehniku 1977.

Slična tehnika transformacije se koristi u Surbaleovom algoritmu (1974) za nalaženje dva nesrazmerna puta minimalne ukupne dužine između dva ista čvora u grafu sa ne-negativnim ivicama.

Opis algoritma

Dzonsonov algoritam se sastoji iz sledećih koraka:

1. Prvo, novi čvor q se dodaje grafu, povezan ivicama težine nula za svaki od čvorova.
2. 1. Drugo, algoritam se koristi, počevši od novog čvora q, da nađe za svaki čvor v minimalnu težinu h(v) puta od q do v. Ako ovaj korak otkrije negativni ciklus, algoritam se prekida.
3. 2. Sledeće ivice originalnog grafa dobijaju nove težine pomoću vrednosti izračunate od strane Belcman-Ford algoritma: ivica od u do v, dužine w(u,v), data je nova dužina w (u,v) + h (u) – h (v).
4. 3. Konačno, q se uklanja, a Dijkstra algoritam se koristi da pronađe najkraće puteve od svakog čvora s do svakog drugog temena sa novom vrednosti u grafu.

Primer

Prve tri faze Dzonson algoritma su prikazane na slici ispod.

Graf na levoj slici ima dve negativne ivice ali nema negativnih ciklusa. U centru se prikazuju nova temena q, najkraći put stabla kako je obračunat po Belcman-Ford algoritmu sa q kao polaznim temenom, a vrednosti h(v) izračunate na svakom drugom čvoru kao dužina najkraćeg puta od q do tog čvora. Imajte na umu da sve ove vrednosti nisu pozitivne, jer q ima nula dužinu ivice od svakog čvora i najkraći put ne može biti duži od te ivice. Sa desne strane je prikazan graf novih vrednosti, formiranih zamenom težine svake ivice w(u,v)sa w (u, v) + h (u) - h (v) . U ovom grafu sa novim vrednostima sve težine ivica su ne-negativne, ali najkraći put između bilo koja dva čvora koristi isti niz ivica kao najkraći put između dva ista čvora u originalnom grafu. Algoritam se završava primenom Dijkstra algoritma za svaki od četiri početna čvora u grafu novih vrednosti.

Ispravnost

U ponovno izmerenom grafu, svi putevi između para s i t čvorova imaju istu količinu h (s) - h (t) dodatu njima. Prethodna izjava se moze dokazati na sledeći način: Neka je p s-t put. Njegova težina W u ponovno izmerenom grafu je data sledećim izrazom:

${\bigl (}w(s,p1)+h(s)-h(p1){\bigr )}+{\bigl (}w(p1,p2)+h(p1)-h(p2){\bigr )}+...+{\bigl (}w(p_{n},t)+h(p_{n})-h(t){\bigr )}.$

Obratite pažnju da svaki$+h(p_{i})$ je otkazan sa $-h(p_{i})$ u prethodnom izrazu uglastim zagradama, dakle, ostaje nam sledeći izraz za W:

${\bigl (}w(s,p1)+w(p1,p2)+...+w(p_{n},t){\bigr )}+h(s)-h(t)$

Obratite pažnju da u zagradama izraza je težina p u originalnoj težini.

Pošto ponovno računanje dodaje isti iznos na težinu svakog s-t puta, put je najkraći put u originalnoj težini ako i samo ako je to najkraći put posle ponovnog računanja. Težina ivica koje pripadaju najkraćem putu od q do bilo kog čvora je nula, a samim tim i dužine najkraćih puteva iz q ka svakom čvoru postaju nula u ponovo izmerenom grafu, ali oni i dalje ostaju najkraći putevi. Prema tome, ne moze biti negativnih ivica: ukoliko ivica uv ima negativnu težinu posle ponovnog računanja, onda nulta dužina puta od q do u zajedno sa svojom ivicom formiraće negativnu dužinu puta od q do v, demantujući činjenicu da svi čvorovi imaju nultu udaljenost od q. Nepostojanje negativnih ivica osigurava optimalnost puteva pronađenih Dijkstra algoritmom. Rastojanja u originalnom grafu mogu se izračunati rastojanjima izračunatih Dijkstra algoritmom u ponovno izmerenom grafu preusmerući ponovno izračunatu transformaciju.

Analiza

Vremenska slozenost ovog algoritma, koristeći Fibonačijev hip u implementaciji Dijkstra algoritma, je O(V²log V + VE): algoritam koristi O(VE) vreme u Belcman-Ford fazi algoritma, i O(V log V + E) za svaki od V instanci Dijkstra algoritma. Dakle, kada je graf proređen, ukupno vreme može da bude brže od Flojd-Varšalovog algoritma, koji rešava isti problem u vremenu O(V³).

Reference

• Black, Paul E. (2004), „Johnson's Algorithm”, Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology .
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. . Section 25.3, "Johnson's algorithm for sparse graphs". стр. 636–640.
• 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 .
• Suurballe, J. W. (1974), „Disjoint paths in a network”, Networks, 14 (2): 125—145, doi:10.1002/net.3230040204 .

Spoljašnje veze

• Boost: All Pairs Shortest Paths