Floyd-Warshallův algoritmus

Floyd-Warshallův algoritmus (Floydův algoritmus) slouží k nalezení nejkratších cest mezi všemi dvojicemi uzlů grafu, který neobsahuje cykly záporné délky. Jeho hlavní výhodou je jeho implementační jednoduchost.

Princip

Floyd-Warshallův algoritmus má na vstupu matici délek, říkejme jí $D^{0}$ . Pokud mezi dvěma uzly $(i,\; j)$ vede hrana délky l, tak tato matice obsahuje na indexu $(i,\; j)$ právě tuto hodnotu. Na diagonále má tato matice samé nuly a na ostatních indexech, které neodpovídají hraně nekonečno. Jinými slovy tato matice obsahuje vzálenosti uzlů, které nevedou skrze žádného prostředníka.

V každé iteraci Floyd-Washallova algoritmu se tato matice přepočítá tak, aby vyjadřovala vzdálenost všech dvojic uzlů skrze postupně se zvětšující množinu přípustných prostředníků. Jednoduše řečeno matice $D^{1}$ bude vyjadřovat vzdálenost všech uzlů s možností využití jednoho (daného) prostředníka, $D^{2}$ vzdálenost při možném využití dvou (daných) prostředníků, $D^{k}$ při možnosti využití k prostředníků.

Tato transformace se dá vyjádřit pro $k \geq 1$ následujícím rekurentním vztahem:

$d_{ij}^{k} = \min(d_{ij}^{k-1}, d_{ik}^{k-1} + d_{kj}^{k-1})$

Protože při trasformaci nemůže dojít k přepisu hodnot, z nichž se počítají prvky nové matice, tak v samotné implementaci stačí použít právě jednu matici pro $D^{i}$ a $D^{i+1}$ .

Matice předchůdců

Výstupem Floyd-Warshallova algoritmu je matice předchůdců. Pokud hledáme cestu mezi uzly $(i,\;j)$ , pak se podíváme na záznam na řádek i, sloupec j. Pokud je pole nulové, pak cesta neexistuje, v opačném případě udává předchůdce koncového uzlu j na této cestě. Postupujeme rekurzivně tímto postupem tak dlouho, dokud není počáteční a koncový uzel totožný.

Čtení cesty z matice předchůdců

Pseudocode

function getPath(p, i, j)
    if i == j then
        write(i)
    else if p[i][j] = 0 then
        write("Cesta neexistuje")
    else
        getPath(p, i, p[i][j])
        write(j)

Detekce cyklů (ne)záporné délky

Za předpokladu, že se na diagonálu matice délek umístí místo nul hodnoty nekonečno, tak algoritmus nalezne cykly (ne)záporné délky, jsou-li v grafu obsaženy, tzn. na diagonále matice předchůdců nebudou obsaženy nuly.

Složitost

Protože má minimalizace ve vnitřním cyklu konstantní složitost, tak je zjevné, že je celková asymptotická složitost algoritmu $O(n^{3})$ .

Kód

Pseudocode

procedure [array] FloydWarshall(D)
    p = new array[n][n]
    for k in 1 to n do
        for i in 1 to n do
            for j in 1 to n do
                if D[i][j] > D[i][k] + D[k][j] then
                    D[i][j] = D[i][k] + D[k][j]
                    p[i][j] = p[k][j]
    return p

Literatura

KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.
HANZÁLEK, Zdeněk. Kombinatorická optimalice, Nejkratší cesty - slides k přednáškám.

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (0): 0

Přečtěte si také

Diskuse

Článek zatím nemá žádné komentáře.