Флојд-Воршалов алгоритам
Из пројекта Википедија
Флојд-Воршалов алгоритам служи за належење накраћих путева између свих чворова у тежинским усмереним графовима.
Садржај |
[уреди] Опис алгоритма
Нека је дат усмерени тежински граф (V, E). Тежина пута између два чвора графа једнака је суми тежина ивица који сачињавају тај пут. Тежине ивица из скупа E могу бити негативне, али ниједан цикличан пут графа не сме имати негативну вредност. За сваки пар чворова алгоритам налази најкраћи пут између њих.
Алгоритам се заснива на следећем:
- Нека су чворови усмереног графа G дати са V = {1, 2, 3, 4, ..., n}. Размотримо даље подскуп {1, 2, 3, ..., k}.
- За сваки пар чворова i, j из V, разматрамо путеве из i у j преко неког од чворова из скупа {1, 2, ..., k} и налазимо онај пут p који има најмању вредност.
[уреди] Псеудокод
Флојд-Воршалов алгоритам можемо помоћу псеудокода представити на следећи начин:
function fw(int[1..n,1..n] graph) { // Иницијализација var int[1..n,1..n] dist := graph var int[1..n,1..n] pred for i from 1 to n for j from 1 to n if dist[i,j] < Infinity pred[i,j] := i // Главна петља алгоритма for k from 1 to n for i from 1 to n for j from 1 to n if dist[i,j] > dist[i,k] + dist[k,j] dist[i,j] = dist[i,k] + dist[k,j] pred[i,j] = pred[k,j] return dist }
[уреди] Временска сложеност
Ако са |V| означимо број чворова графа, тада је временска сложеност тачно О(|V|3).