Сурбалов алгоритам

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) и објавио 1974.

Главна идеја алгоритма јесте да користи Дајкстрин алгоритам да пронађе један пут, потом изврши измене над тежинама грана, и након тога поново позове Дајкстрин алгоритам. Измене над тежинама су сличне изменама које изводи Џонсонов алгоритам, не мења се ненегативност грана и промене су такве да омогућавају да поновни позив Дајкстриног алгоритма врати коректан резултат.

Проблем одвојених путева је блиско повезан са проблемом минималне цене, и у овом случају постоје два елемента, ток (енгл. flow), а чворови имају величину капацитет (енгл. capacity).

Дефиниције

Нека је Г тежински усмерени граф са ненегативним тежинама, где је V скуп од н чворова, Е скуп од м грана. Дефинишемо чвор с из скупа V као почетни чвор, и чвор т из скупа Е као крајњи чвор. Пошто је граф тежински, за сваку грану (у,в) дата је тежина коју ћемо означавати са w(у,в). Дефинишемо д(с,у) као најкраћи пут од чвора у до чвора в у коренском стаблу где је корен чвор у.

Алгоритам

Сурбалов алгоритам се састоји из следећих 5 фундаменталних корака:

1. Пронађи стабло најкраћих путева Т чији је корен чвор с користећи Дајкстрин алгоритам. Стабло Т за сваки чвор у, садржи најкраћи пут од с до у. Нека је П₁ најкраћи пут са најмањом ценом од с до т. Гране у стаблу Т називамо гране стабла, а гране које нису у Т, називамо гране које нису ушле у стабло.
2. Промени тежину сваке гране у графу модификовањем тежине w(у,в) за сваку грану (у,в) на следећи начин: w'(у,в) = w(у,в) − д(с,в) + д(с,у). Сада све гране које су ушле у стабло имају цену 0, а гране ван стабла задржавају својство да су им тежине ненегативне.
3. Креирај помоћни граф Г_т од графа Г тако што се уклањају гране из Г које улазе у с, и тако што се окреће смер гранама на путу П₁ чија је тежина једнака нули.
4. Пронађи најкраћи пут П₂ у помоћном графу Г_т помоћу Дајкстриног алгоритма.
5. Одбаци окренуте гране из П₂ са оба пута. Преостале гране са П₁ и П₂ формирају подграф са две одлазне гране из с, две гране улазне ка т, и са једном одлазном и једном долазном граном са све преостале чворове у графу. Тиме се подграф састоји од два развојена пута од с до т, и потенцијално неким додатним циклусима. Вратити два раздвојена пута из подграфа.

Пример

Следећи пример илуструје како Сурбалов алгоритам проналази најкраћи пар несуседних путева од А до Ф.

Слика А илуструје тежински граф Г.

Слика Б илуструје израчунавање најкраћег пута П₁ одА до Ф (А–Б–D–Ф).

Слика C приказује стабло најкраћих путева Т са кореном у А, а потом и израчуната растојања од А ка свим осталим чворовима.

Слика D приказује ажуриране цене сваке гране као и гране у путу 'П₁ које су обрнуте.

Слика Е израчунава се пут П₂ у помоћном графу Г_т (А–C–D–Б–Е–Ф).

Слика Ф илуструје путеве П₁ и П₂.

Слика Г проналази се најкраћи пар несуседних путева комбиновањем путева П₁ и П₂ а потом се одбацују обнути путеви (Б–D). Као резултат добија се пар најлраћих несуседних путева (А–Б–Е–Ф) и (А–C–D–Ф).

Коректност алгоритма

Тежина било којег пута од чвора с до чвора т у промењем графу тежина је једнак тежини оригиналног графа умањено за д(с,т). Тиме, два најкраћа одвојена пута која се издвајају алгоритмом су иста као и два најкраћа пута у почетном графу, иако имају другачије тежине.

Сложеност

Алгоритам захтева две итерације Дајкстриног алгоритма. Користећи фибоначијев хип, обе итерације могу да се изведу у времену О(м + н лог н) на графу са н чворова и м грана, тако да је сложеност алгоритма О(м + н лог н).