Graf a jeho matice délek

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í . Pokud mezi dvěma uzly vede hrana délky l, tak tato matice obsahuje na indexu 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 bude vyjadřovat vzdálenost všech uzlů s možností využití jednoho (daného) prostředníka, vzdálenost při možném využití dvou (daných) mezilehlých uzlů, při možnosti využití m mezilehlých uzlů.

Tato transformace se dá vyjádřit pro následujícím rekurentním vztahem:

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 a .

Kód

procedure [array] FloydWarshall(D, P)
    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

    /**
     * Floyd-Warshall algorithm. Finds all shortest paths among all pairs of nodes
     * @param d matrix of distances (Integer.MAX_VALUE represents positive infinity)
     * @return matrix of predecessors
     */
    public static int[][] floydWarshall(int[][] d) {
        int[][] p = constructInitialMatixOfPredecessors(d);
        for (int k = 0; k < d.length; k++) {
            for (int i = 0; i < d.length; i++) {
                for (int j = 0; j < d.length; j++) {
                    if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) {
                        continue;                  
                    }
                    
                    if (d[i][j] > d[i][k] + d[k][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                        p[i][j] = p[k][j];
                    }

                }
            }
        }
        return p;
    }

    /**
     * Constructs matrix P0
     * @param d matrix of lengths
     * @return P0
     */
    private static int[][] constructInitialMatixOfPredecessors(int[][] d) {
        int[][] p = new int[d.length][d.length];
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d.length; j++) {
                if (d[i][j] != 0 && d[i][j] != Integer.MAX_VALUE) {
                    p[i][j] = i;
                } else {
                    p[i][j] = -1;
                }
            }
        }
        return p;
    }

Složitost

Protože má minimalizace ve vnitřním cyklu konstantní složitost, tak je zjevné, že je celková asymptotická složitost algoritmu .

Příklad

Matice předchůdců

Aby bylo možné zrekonstruovat cesty mezi jednotlivými uzly, tak Floyd-Warshallův algoritmus generuje také matici předchůdců. Tuto matici, která je výstupem algoritmu, čteme následujícím způsobem: pokud hledáme cestu mezi uzly , pak se podíváme na záznam na řádek , sloupec . Pokud je pole nulové, pak cesta neexistuje, v opačném případě udává předchůdce koncového uzlu na této cestě. Tento postup rekurzivně opakujeme tak dlouho, dokud není předchůdce roven počátečnímu uzlu .

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

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)

Příklad

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.

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.