Surbalov algoritam

С Википедије, слободне енциклопедије

Surbalov algoritam je grafovski algoritam koji pronalazi dva nesusedna puta u nenegativnom težinskom usmerenog grafu, tako da oba puta povezuju par zadatih čvorova i težina grana je minimalna. Algoritam je konstruisao J. W. Surbal (енгл. J.W. Suurballe) i objavio 1974. [1][2][3]

Glavna ideja algoritma jeste da koristi Dajkstrin algoritam da pronađe jedan put, potom izvrši izmene nad težinama grana, i nakon toga ponovo pozove Dajkstrin algoritam. Izmene nad težinama su slične izmenama koje izvodi Džonsonov algoritam, ne menja se nenegativnost grana i promene su takve da omogućavaju da ponovni poziv Dajkstrinog algoritma vrati korektan rezultat.

Problem odvojenih puteva je blisko povezan sa problemom minimalne cene, i u ovom slučaju postoje dva elementa, tok (енгл. flow), a čvorovi imaju veličinu kapacitet (енгл. capacity).

Definicije[уреди | уреди извор]

Neka je G težinski usmereni graf sa nenegativnim težinama, gde je V skup od n čvorova, E skup od m grana. Definišemo čvor s iz skupa V kao početni čvor, i čvor t iz skupa E kao krajnji čvor. Pošto je graf težinski, za svaku granu (u,v) data je težina koju ćemo označavati sa w(u,v). Definišemo d(s,u) kao najkraći put od čvora u do čvora v u korenskom stablu gde je koren čvor u.

Algoritam[уреди | уреди извор]

Surbalov algoritam se sastoji iz sledećih 5 fundamentalnih koraka:

  1. Pronađi stablo najkraćih puteva T čiji je koren čvor s koristeći Dajkstrin algoritam. Stablo T za svaki čvor u, sadrži najkraći put od s do u. Neka je P1 najkraći put sa najmanjom cenom od s do t. Grane u stablu T nazivamo grane stabla, a grane koje nisu u T, nazivamo grane koje nisu ušle u stablo.
  2. Promeni težinu svake grane u grafu modifikovanjem težine w(u,v) za svaku granu (u,v) na sledeći način: w'(u,v) = w(u,v) − d(s,v) + d(s,u). Sada sve grane koje su ušle u stablo imaju cenu 0, a grane van stabla zadržavaju svojstvo da su im težine nenegativne.
  3. Kreiraj pomoćni graf Gt od grafa G tako što se uklanjaju grane iz G koje ulaze u s, i tako što se okreće smer granama na putu P1 čija je težina jednaka nuli.
  4. Pronađi najkraći put P2 u pomoćnom grafu Gt pomoću Dajkstrinog algoritma.
  5. Odbaci okrenute grane iz P2 sa oba puta. Preostale grane sa P1 i P2 formiraju podgraf sa dve odlazne grane iz s, dve grane ulazne ka t, i sa jednom odlaznom i jednom dolaznom granom sa sve preostale čvorove u grafu. Time se podgraf sastoji od dva razvojena puta od s do t, i potencijalno nekim dodatnim ciklusima. Vratiti dva razdvojena puta iz podgrafa.


Primer[уреди | уреди извор]

Sledeći primer ilustruje kako Surbalov algoritam pronalazi najkraći par nesusednih puteva od A do F.

Slika A ilustruje težinski graf G.

Slika B ilustruje izračunavanje najkraćeg puta P1 odA do F (ABDF).

Slika C prikazuje stablo najkraćih puteva T sa korenom u A, a potom i izračunata rastojanja od A ka svim ostalim čvorovima.

Slika D prikazuje ažurirane cene svake grane kao i grane u putu 'P1 koje su obrnute.

Slika E izračunava se put P2 u pomoćnom grafu Gt (ACDBEF).

Slika F ilustruje puteve P1 i P2.

Slika G pronalazi se najkraći par nesusednih puteva kombinovanjem puteva P1 i P2 a potom se odbacuju obnuti putevi (BD). Kao rezultat dobija se par najlraćih nesusednih puteva (ABEF) i (ACDF).

Korektnost algoritma[уреди | уреди извор]

Težina bilo kojeg puta od čvora s do čvora t u promenjem grafu težina je jednak težini originalnog grafa umanjeno za d(s,t). Time, dva najkraća odvojena puta koja se izdvajaju algoritmom su ista kao i dva najkraća puta u početnom grafu, iako imaju drugačije težine.

Složenost[уреди | уреди извор]

Algoritam zahteva dve iteracije Dajkstrinog algoritma. Koristeći fibonačijev hip, obe iteracije mogu da se izvedu u vremenu O(m + n log n) na grafu sa n čvorova i m grana, tako da je složenost algoritma O(m + n log n).

Reference[уреди | уреди извор]

  1. ^ Suurballe, J. W. (1974), „Disjoint paths in a network”, Networks, 4 (2): 125—145, doi:10.1002/net.3230040204 
  2. ^ Suurballe, J. W.; Tarjan, R. E. (1984), „A quick method for finding shortest pairs of disjoint paths” (PDF), Networks, 14 (2): 325—336, doi:10.1002/net.3230140209 
  3. ^ Bhandari, Ramesh (1999), „Suurballe's disjoint pair algorithms”, Survivable Networks: Algorithms for Diverse Routing, Springer-Verlag, стр. 86—91, ISBN 978-0-7923-8381-9