Graf

    \\begin{pmatrix}
    0 & 5 & \\infty & 2 & \\infty \\\\
    \\infty & 0 & 2 & \\infty & \\infty \\\\
    3 & \\infty & 0 & \\infty & 7 \\\\
    \\infty & \\infty & 4 & 0 & 1 \\\\
    1 & 3 & \\infty & \\infty & 0 \\\\
    \\end{pmatrix}
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í 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) mezilehlých uzlů, D^{m} při možnosti využití m mezilehlých uzlů.

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


D_{ij}^{m} = \\min(D_{ij}^{m-1}, D_{ik}^{m-1} + D_{kj}^{m-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}.

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 O(\\vert U \\vert ^{3}).


Příklad


    \\begin{matrix}
  
      D_{0} = 
      \\begin{pmatrix}
        0 & 5 & \\infty & 2 & \\infty \\\\
        \\infty & 0 & 2 & \\infty & \\infty \\\\
        3 & \\infty & 0 & \\infty & 7 \\\\
        \\infty & \\infty & 4 & 0 & 1 \\\\
        1 & 3 & \\infty & \\infty & 0 \\\\
      \\end{pmatrix}
    
      &
      
      D_{1} =
      
      \\begin{pmatrix}
        0 & 5 & \\infty & 2 & \\infty \\\\
        \\infty & 0 & 2 & \\infty & \\infty \\\\
        3 & 8 & 0 & 5 & 7 \\\\
        \\infty & \\infty & 4 & 0 & 1 \\\\
        1 & 3 & \\infty & 3 & 0 \\\\
      \\end{pmatrix}    
      
      &
      
      D_{2} =
      
      \\begin{pmatrix}
        0 & 5 & 7 & 2 & \\infty \\\\
        \\infty & 0 & 2 & \\infty & \\infty \\\\
        3 & 8 & 0 & 5 & 7 \\\\
        \\infty & \\infty & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix}       
      \\\\ 
      
      \\\\
      
      D_{3} =
      
      \\begin{pmatrix}
        0 & 5 & 7 & 2 & 14 \\\\
        5 & 0 & 2 & 7 & 9 \\\\
        3 & 8 & 0 & 5 & 7 \\\\
        7 & 12 & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      D_{4} =
      
      \\begin{pmatrix}
        0 & 5 & 6 & 2 & 3 \\\\
        5 & 0 & 2 & 7 & 8 \\\\
        3 & 8 & 0 & 5 & 6 \\\\
        7 & 12 & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      D_{5} =
      
      \\begin{pmatrix}
        0 & 5 & 6 & 2 & 3 \\\\
        5 & 0 & 2 & 7 & 8 \\\\
        3 & 8 & 0 & 5 & 6 \\\\
        2 & 4 & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix}       
      
      
    \\end{matrix}

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 (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ě. Tento postup rekurzivně opakujeme tak dlouho, dokud není předchůdce roven počátečnímu uzlu i.


  \\begin{matrix}
  P_{ij}^{(0)} =   \\begin{cases}
   0       & \\;\\;\\;\\;\\; \\text{if}\\;\\;\\; i = j\\;\\; or \\;\\; D_{ij} = \\infty \\\\
   i       & \\;\\;\\;\\;\\; \\text{ve všech ostatních případech}
  \\end{cases}
  
  \\\\\\\\
  
  P_{ij}^{(m)} =   \\begin{cases}
   P_{ij}^{(m-1)}      & \\;\\;\\;\\;\\; \\text{if}\\;\\;\\; D_{ij}^{(m-1)} \\leq  D_{ik}^{(m-1)} + D_{kj}^{(m-1)}\\\\
   P_{kj}^{(m-1)}      & \\;\\;\\;\\;\\; \\text{if}\\;\\;\\; D_{ij}^{(m-1)} \\gt  D_{ik}^{(m-1)} + D_{kj}^{(m-1)}
  \\end{cases}  
  
  \\end{matrix}

Č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


    \\begin{matrix}
  
      P_{0} = 
      \\begin{pmatrix}
        0 & 1 & 0 & 1 & 0 \\\\
        0 & 0 & 2 & 0 & 0 \\\\
        3 & 0 & 0 & 0 & 3 \\\\
        0 & 0 & 4 & 0 & 4 \\\\
        5 & 5 & 0 & 0 & 0 \\\\
      \\end{pmatrix}
    
      &
      
      P_{1} =
      
      \\begin{pmatrix}
        0 & 1 & 0 & 1 & 0 \\\\
        0 & 0 & 2 & 0 & 0 \\\\
        3 & 1 & 0 & 1 & 3 \\\\
        0 & 0 & 4 & 0 & 4 \\\\
        5 & 5 & 0 & 1 & 0 \\\\
      \\end{pmatrix}    
      
      &
      
      P_{2} =
      
      \\begin{pmatrix}
        0 & 1 & 2 & 1 & 0 \\\\
        0 & 0 & 2 & 0 & 0 \\\\
        3 & 1 & 0 & 1 & 3 \\\\
        0 & 0 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix}       
      \\\\ 
      
      \\\\
      
      P_{3} =
      
      \\begin{pmatrix}
        0 & 1 & 2 & 1 & 3 \\\\
        3 & 0 & 2 & 1 & 3 \\\\
        3 & 1 & 0 & 1 & 3 \\\\
        3 & 1 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      P_{4} =
      
      \\begin{pmatrix}
        0 & 1 & 4 & 1 & 4 \\\\
        3 & 0 & 2 & 1 & 4 \\\\
        3 & 1 & 0 & 1 & 4 \\\\
        3 & 1 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      P_{5} =
      
      \\begin{pmatrix}
        0 & 1 & 4 & 1 & 4 \\\\
        3 & 0 & 2 & 1 & 4 \\\\
        3 & 1 & 0 & 1 & 4 \\\\
        5 & 5 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix}       
      
      
    \\end{matrix}

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.







Doporučujeme