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

Из пројекта Википедија

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

Садржај

[уреди] Опис алгоритма

Нека је дат усмерени тежински граф (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).

[уреди] Спољашње везе