Suurballe algoritmus

A Suurballe  -féle algoritmus egy olyan algoritmus, amely két nem metsző (nincs közös él) útvonalat keres egy irányított gráfban , nem negatív súllyal úgy, hogy mindkét út ugyanazt a csúcspárt köti össze, és minimális közös hosszuk legyen [1] .

Az algoritmus rövid leírása

Az algoritmust John Suurballe javasolta, és 1974-ben publikálták [2] . A Suurballe algoritmusának fő ötlete az, hogy Dijkstra algoritmusát használja az elérési út megkeresésére, a gráf élsúlyainak módosítására, majd a Dijkstra algoritmus másodszori futtatására. Az algoritmus kimenete két útvonal kombinálásával, az ezen utak által ellentétes irányban áthaladó élek eldobásával, a fennmaradó élek felhasználásával pedig olyan útvonalak kialakításával jön létre, amelyek az algoritmus kimeneteként szolgálnak.

A súlymódosítás hasonló a Johnson-algoritmusban alkalmazott súlymódosításhoz, és a súlyokat nem negatívan tartja, lehetővé téve a Dijkstra-algoritmus második példányának, hogy megtalálja a helyes második utat.

A minimális súllyal rendelkező két diszjunkt út megtalálásának problémája a minimális költségű áramlási probléma speciális esetének tekinthető , ahol van egy kettes méretű "áramlás", amelynek mindegyik élének egységnyi "kapacitása" van. A Suurballe-féle algoritmus a minimális költségű áramlási algoritmus egy speciális eseteként is felfogható, amely ismételten a lehető legnagyobb áramlást haladja át a legrövidebb úton.

A Suurballe algoritmusa által talált első út a kezdeti (nulla) áramlás legrövidebb útja, a Suurballe algoritmusa által talált második út pedig a maradék gráf legrövidebb útja, miután az egységáramot áthaladta az első útvonalon.

Definíciók

Legyen G súlyozott irányított gráf V csúcskészlettel és E élhalmazzal (A ábra). Legyen s forrás G -ben , t pedig nyelő. Legyen minden él ( u , v ) E - ben az u csúcstól a v csúcsig egy nem negatív w ( u , v ) költséggel .

Határozzuk meg d( s , u ) -t az s csúcsból az u csúcshoz vezető legrövidebb út költségeként az s -ben gyökerező legrövidebb útfában ( C ábra).

Megjegyzés: A csomópontot és a csúcsot gyakran felcserélve használják.

Algoritmus

A Suurballe algoritmus a következő lépéseket hajtja végre:

  1. Az s csomópontban gyökerező T legrövidebb útvonalfát Dijkstra algoritmusának futtatásával találjuk meg (C ábra). Ez a fa bármely u csúcshoz tartalmazza az s -től u -ig vezető legrövidebb utat . Legyen P 1 a legkisebb költségű út s -től t -ig (B ábra). A T fa éleit faéleknek , a fennmaradó éleket pedig (a C ábrán nem látható éleket) fán kívüli éleknek nevezzük .
  2. Módosítjuk a gráf minden élének költségét úgy, hogy az egyes élek w ( u , v ) költségét ( u , v ) -ra cseréljük . Az ármódosító függvény szerint a fa összes élének költsége 0 lesz, a fán kívüli élek ára pedig nem negatív. Például ha , akkor ha , akkor

  3. Létrehozunk egy G -ből képzett G t maradékgráfot úgy, hogy a P 1 út mentén eltávolítjuk G éleit , amelyek s felé irányulnak , majd a pálya mentén megfordítjuk a nulla hosszúságú élek irányait (D ábra).
  4. Keresse meg a legrövidebb utat a maradék gráfban a Dijkstra-algoritmus futtatásával (E ábra).
  5. Mindkét útról eldobjuk a P 2 pálya hátsó éleit. A P 1 és P 2 utak fennmaradó élei egy részgráfot alkotnak, amelynek két kimenő éle s , két bejövő él t -ben , és egy bejövő és egy kimenő él minden fennmaradó csúcsban. Ezért ez a részgráf két él nélküli útból áll s -től t -ig, és esetleg néhány további (nulla hosszúságú) ciklusból. Az algoritmus két nem metsző (élekkel) utat ad vissza egy részgráfból.

Példa

A következő példa bemutatja, hogy a Suurballe algoritmusa hogyan találja meg a legrövidebb nem átfedő útvonalpárt A - tól F -ig .

Az A ábra egy súlyozott G grafikont mutat .

A B ábra kiszámítja a legrövidebb P 1 utat A -tól F -ig ( A - B - D - F ).

A C ábra mutatja az A -ban gyökerező legrövidebb T útfát és az A - tól bármely csúcsig ( u ) számított távolságokat .

A D ábra a G t maradék gráfot mutatja az egyes élek frissített költségével és a P 1 út élei megfordítva.

Az E ábra kiszámítja a G t ( A - C - D - B - E - F ) maradék gráfban a P 2 utat.

Az F ábra mindkét P 1 és P 2 utat mutatja .

A G ábra a P 1 és P 2 utak éleinek kombinálásával és a két út ( B - D ) közötti közös, egymással ellentétes ívek elvetésével találja meg a nem metsző (él) utak legrövidebb párját . Ennek eredményeként a legrövidebb nem metsző útpárt kapjuk ( A - B - E - F ) és ( A - C - D - F ).

Helyesség

Az s -től t -ig tartó bármely út súlya a módosított súlyrendszerben megegyezik az eredeti gráf súlyával mínusz d( s , t ) . Ezért a súlyok módosítása után a két legrövidebb nem metsző út ugyanaz a két legrövidebb út lesz az eredeti gráfban, bár a súlyozás eltérő lesz.

A Suurballe-féle algoritmus a legrövidebb út módszereinek egy speciális eseteként fogható fel egy minimális költségáram megtalálására , amelynek teljes áramlása s és t között kettő . A súlyok módosítása nem befolyásolja az algoritmus által talált utakat, csak azok súlyát. Így az algoritmus helyessége a legrövidebb út megtalálásának módszerének helyességéből következik.

Elemzés és futási idő

Ehhez az algoritmushoz a Dijkstra-algoritmus két iterációja szükséges. Fibonacci kupacok használata esetén mindkét iteráció időben befejezhető , ahol és a csúcsok és élek száma. Így ugyanezek a korlátok vonatkoznak a Suurballe-féle algoritmusra is.

Változatok

A Suurballe-algoritmus egy változata, amint azt fent leírtuk, olyan útvonalakat talál, amelyek nem osztoznak éleken, de esetleg osztoznak csúcsokon. Ugyanezt az algoritmust használhatja olyan utak keresésére, amelyeknek nincs közös csúcsuk, ha minden csúcsot egy pár szomszédos csúcsra cserél, az egyikben a forráscsúcs összes bejövő u-in íve , a másikban az összes kimenő u-out ívével . Két közös él nélküli út ebben a módosított gráfban szükségszerűen megfelel két közös csúcs nélküli útnak az eredeti gráfban, és fordítva, így a Suurballe-algoritmusnak a módosított gráfra történő alkalmazása az eredeti gráfban közös csúcsok nélküli két út felépítéséhez vezet. A Suurballe eredeti, 1974-es algoritmusa egy út nélküli változat volt, amelyet 1984-ben Suurballe és Tarjan kiterjesztett egy út nélküli él nélküli verzióra [3] .

Dijkstra algoritmusának egy módosított változatát használva, amely egyidejűleg számítja ki a távolságokat a G t gráfok minden t csúcsától, az is lehetséges, hogy az adott s csúcstól a gráf bármely másik csúcsáig tartó legrövidebb utak teljes hosszát időarányosan megtaláljuk. a Dijkstra-algoritmus egy futtatásának munkájához.

Megjegyzés: Egy csúcs particionálásával kapott szomszédos csúcspárt nulla költségű orientált ív köti össze a bejövő íveket tartalmazó csúcstól a kimenő ívekkel rendelkező csúcsig. Az s-out lesz a forrás , a t-in pedig a mosogató .

Jegyzetek

  1. ↑ Bhandari, 1999 , p. 86–91.
  2. ↑ Suurballe, 1974 , p. 125–145.
  3. ↑ Suurballe, Tarjan, 1984 , p. 325–336.

Irodalom