Флојд-Воршалов алгоритам

У рачунарству Флојд-Воршалов алгоритам алгоритам (понекад се зове и Roy-Floyd алгоритам или WFI алгоритам, откад је Bernard Roy описао алгоритам 1959) је алгоритам анализе графова за налажење најкраћих путања у тежинском, усмереном графу. Једно извршење алгоритма ће наћи најкраће путање између свих парова чворова. Floyd-Warshall алгоритам је пример динамичког програмирања.

Опис алгоритма

Флојд-Воршалов алгоритам упоређује све могуће путеве у графу између сваког пара чворова. Он је у стању да уради то са само V3 поређења (то је изузетно обзиром да у графу може бити V2 грана а свака грана се проверава). Алгоритам то ради тако што постепено побољшава процену најкраћег пута између два чвора, док не буде познато да је процена оптимална.

Нека је дат граф G са чворовима V, означеним од 1 до N. Даље, нека постоји функција najkraciPut(i, ј,k) која враћа најкраћи могући пут од i до j користећи само чворове од 1 до k као међутачке на путу. Сада, користећи ову функцију, циљ је наћи најкраћи пут од сваког i до сваког j користећи само чворове од 1 до k+1. Постоје два кандидата за овај пут: или прави најкраћи пут користи само чворове из скупа (1...k); или постоји неки пут који иде од i до k+1, затим од k+1 до j који је бољи. Зна се да је најбољи пут од i до j, који користи само чворове од 1 до k, дефинисан функцијом najkraciPut(i, ј,k), и очито је да кад би постојао бољи пут од и до k+1 до j, дужина овог пута би била конкатенација најкраћег пута од i до k+1 (користећи чворове у (1...k)) и најкраћег пута од k+1 до j (такође користећи чворове у (1...k)).

Дакле, може се дефинисати najkraciPut(i, ј,k) преко рекурентне формуле: ${\textrm {najkraciPut}}(i,j,k)=\min({\textrm {najkraciPut}}(i,j,k-1),{\textrm {najkraciPut}}(i,k,k-1)\,+\,{\textrm {najkraciPut}}(k,j,k-1));\,\!$

${\textrm {najkraciPut}}(i,j,0)={\textrm {edgeCost}}(i,j);\,\!$

Ова формула је срж Флојд Воршал-а. Алгоритам ради тако што прво израчуна najkraciPut(i, ј,1) за све (i,j) парове, затим користећи то налази najkraciPut(i,j,2) за све парове (i,j), итд. Овај процес се наставља док се не стекне услов k=n. И, нађен је најкраћи пут за све (i,j) парове користећи потребне међучворове.

Псеудокод

Када се израчунава k-ти случај згодно је што се може снимити прорачун преко информације сачуване од израчунавања случаја k-1. То значи да алгоритам користи квадратну меморију. Обратити пажњу и уочити почетне услове:

1 /* Подразумева се да постоји функција edgeCost(i,j,k) која враћа  цену од i до j
2    (бесконачност ако је нема).
3    Такође се подразумева да је n број чворова и edgeCost(n,n)=0
4 */
5
6 int path[][];
7 /* А .- матрица димензије 2. У сваком кораку алгоритма, path[i][j] је најкраћи пут
8    од i до j користећи међувредности у (1..k-1).  Сваки path[i][j] је иницијализован на
9    edgeCost(i,j).
10 */
11
12 procedure FloydWarshall ()
13    for k: = 0 to n − 1
14    begin
15       for each (i,j) in (0..n − 1)
16       begin
17          path[i][j] = min (path[i][j], path[i][k]+path[k][j] );
18       end
19    end
20 endproc

Понашање са негативним циклусима

За нумерички валидан излаз, Флојд-Воршалов алгоритам претпоставља да нема негативних циклуса (у ствари, између било ког пара чворова које чине негативни циклус најкраћи пут није добро дефинисан зато што пут може бити бесконачно мали). Ипак, ако постоје негативни циклуси, Флојд-Воршалов алгоритам се може искористити да се они открију. Ако се изврши алгоритам још једном, неке путање се могу скратити али не постоји гаранција да ће се између свих чворова, између којих путеви могу бити бесконачно мали, скратити пут. Ако је број у дијагонали матрице пута негативан, то је довољан је и неопходан услов да дати чвор припада негативном циклусу.

Временска сложеност и Анализа

Да би нашли свих ${\mathit {n}}^{2}$ од ${\mathcal {W}}_{k}$ од оних ${\mathcal {W}}_{\mathit {k-1}}$ потребно је $2{\mathit {n}}^{2}$ операција над битовима. Како се почиње са ${\mathcal {W}}_{0}={\mathcal {W}}_{\mathcal {R}}$ и рачуна низ од n „zero-one“ (матрица чији су сви елементи или 0 или 1) матрица ${\mathcal {W}}_{1}$ , ${\mathcal {W}}_{2}$ , $...$ , ${\mathcal {W}}_{\mathit {n}}={\mathcal {M}}_{{\mathcal {R}}^{*}}$ , укупан број операција над битовима је ${\mathit {n}}\times 2{\mathit {n}}^{2}=2{\mathit {n}}^{3}$ . Сложеност алгоритма је $\Theta (n^{3})$ и може да се реши детерминистичком машином у полиномијалном времену.

Ако се са |V| означи број чворова графа, тада је временска сложеност тачно О(|V|³).

Примене и генерализације

Флојд-Воршалов алгоритам, између осталог, може бити кориштен у решавању следећих проблема:

Најкраћи путеви у усмереним графовима (Флојдов алгоритам).
Транзитивно затворење у усмереним графовима (Воршалов алгоритам). У Воршаловој првобитној формулацији алгоритма, граф је безтежински и репрезентован је Буловском матрицом. Затим је операција сабирања замењена логичком конјукцијом (AND) и операција минимума логичком дисјункцијом (PR).
За налажење регуларног израза који описује регуларни језик прихваћен коначним аутоматом (Клинијев алгоритам).
Инверзија реалних матрица (Гаус-Жорданов алгоритам).
Оптимално рутирање. Код ове примене интересује нас налажење пута са максималним протоком између два чвора. То значи да уместо минимум у горњем псеудокоду ми узимамо максимум. Тежине грана представљају фиксиране препреке за проток. Тежине путева представљају загушења; зато се горња операција сабирања замењује операцијом минимума.
Провера бипартитности неусмереног графа.

Спољашње везе