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

У рачунарству Флојд-Воршалов алгоритам алгоритам (понекад се зове и 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) преко рекурентне формуле:

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

други језици