Implementácia algoritmu Floyd-Warshall - Najkratšia cesty

V minulej lekcii, Tok v sieti a Dinicův algoritmus na hľadanie maximálneho toku , sme si ukázali definície toku v sieti, súvisiacich pojmov a implementácia jedného z algoritmov na hľadanie maximálneho toku zvaného Dinicův algoritmus.

S teóriou okolo hľadanie najkratšej cesty v grafe sme sa už stretli v lekcii Hľadanie najkratšej cesty v grafe, kde tiež nájdete ďalšie teóriu k problematike hľadanie najkratšej cesty v grafe.

V tomto článku sa budeme venovať samotnej implementácii algoritmu Floyd-Warshall. Tento algoritmus sa používa, ak chceme mať niekde uloženú maticu vzdialeností medzi všetkými vrcholmi grafu a pomocou nej zistiť najkratšiu cestu medzi jednotlivými vrcholmi. V tom je ale problém algoritmu. Jeho časová a hlavne pamäťová zložitosť je O (n ^3). Jednoducho totiž prejde všetky možné cesty medzi všetkými dvojicami vrcholov. Pri milióna vrcholov je to už značná pálka ... Ale na druhú stranu je algoritmus jednoduchý a napíšeme ho hneď

Opis algoritmu

Pre ilustráciu sa ešte raz pozrime na opis algoritmu. Majme ohodnotený graf G, ktorý máme uložený ako maticu vzdialeností. Ak nás teda napr. Zaujíma vzdialenosť medzi vrcholmi 1 a 2, zistíme ju ako G[1][2]. A ako teda nájdeme najkratšej cesty medzi všetkými možnými dvojicami vrcholov v grafe? Budeme postupovať takto:

pro každé k od 1 do n
     pro každé i od 1 do n
      pro každé j od 1 do n
        pokud G[i][j] > G[i][k] + G[k][j] potom
            G[i][j] = G[i][k] + G[k][j]

Pre každý vrchol v grafe nájdeme druhý vrchol (tým máme dvojicu) ak nim nájdeme tretí vrchol (skúsime si to cez neho skrátiť). Ďalej chceme povedať, že ak je cesta medzi dvomi vrcholmi dlhšia ako cesta cez tretiu vrchol, použijeme menšiu vzdialenosť cez tretiu vrchol. To je celá mágia Floyd-Warshalla. Keďže sa vzdialenosť hneď prepíše v matici vzdialeností, bude nová skratka použitá aj pre ďalšie priechody.

Podobný algoritmus vykonávame bežne, napr. Keď je niekde zápcha a chceme sa dostať do mesta A rýchlejšie, vezmeme to cez nejaké mesto B a vyhneme sa zdržania. Tu to len prepisujeme do kódu.

Implementácia

Myslím, že vieme, čo chceme robiť. Poďme algoritmus teda prepísať do kódu.

Inicializácia

Začneme inicializáciou:

public class FloydWarshall {

       private int[][] adj;
       private int nekonecno = Integer.MAX_VALUE;

       private FloydWarshall(int uzly) {
            this.adj = new int[uzly][uzly];
            for (int i = 0; i < adj.length; i++) {
                for (int j = 0; j < adj[i].length; j++) {
                    if (i == j)
                        this.adj[i][j] = 0;
                    else
                        this.adj[i][j] = nekonecno;
                }
            }
       }
}

Zadefinujeme si maticu a nekonečno. Pripravíme si našu maticu vzdialeností ako nové pole typu int. Parameter uzly označuje počet uzlov.

Pomocou for cyklov prejdeme všetky dvojice uzlov i, j. Tie, ktoré sa rovnajú, sú 0, pretože vzdialenosť z nejakého vrcholu do toho istého vrcholu je 0. Ostatné hodnoty vzdialeností sú nekonečno, pretože ešte nemáme pridanej ohodnotené hrany. nekonečno je teda naša východisková hodnota a označuje, že medzi vrcholmi zatiaľ nie je cesta.

Pridanie hrany

Ďalej si pridáme metódu na pridanie hrany do matice vzdialeností medzi všetkými vrcholmi v grafe. Ako parametre uvedieme medzi aké vrcholy hranu vkladáme a aká je medzi nimi vzdialenosť (teda aká je váha hrany):

private void pridejHranu(int u, int v, int vaha) {
    adj[u][v] = Math.min(adj[u][v], vaha);
}

Vzdialenosť medzi dvoma hranami pridáme pomocou minima z hodnoty adj[u][v] a váhy hrany (vzdialenosti). V maticu sú hodnoty uložené po inicializácii (teda 0 alebo nekonečno). Ak je tu 0, chceme ju zachovať. V prípade nekonečna hodnotu prepíšeme na danú váhu hrany.

Samotnej hľadanie

Postup ďalej k už spomenutej trojici for cyklov, ktorými prejdeme našu maticu:

private void spust() {
    for (int k = 0; k < adj.length; k++) {
        for (int i = 0; i < adj.length; i++) {
            if (adj[i][k] >= horniMez)
                continue;
            for (int j = 0; j < adj.length; j++) {
                if (adj[k][j] >= horniMez)
                    continue;
                adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }
}

Ak narazíme v matici vzdialeností na hranu, ktorá má nejakú váhu, čiže vzdialenosť medzi k a j je menšie ako nekonečno, tak potom skúsime, či je vzdialenosť medzi k a j väčšie ako vzdialenosť medzi i k a i j. Čo je to vlastne za podmienku?

Ide nám o to, či je rýchlejší priama cesta medzi dvoma vrcholmi, alebo je rýchlejší ísť cez tretiu vrchol. A to je presne to, čo robí testovanie najkratšie vzdialenosti. No a to je celý algoritmus. Je elegantný, jednoduchý, ale bohužiaľ náročný na výpočet. Tri for cykly v sebe nám dajú kubickú O() notáciu.

Vidíme, že výsledok upravujeme priamo v matici vzdialeností.

Vypíšme výsledok

Keďže sme už s algoritmom hotoví, tak si urobme radosť a ešte si urobme po dobre odvedenej práci pekný výpis

@Override
public String toString() {
    String res = "";
    for (int i = 0; i < this.adj.length; i++) {
        for (int j = 0; j < this.adj[i].length; j++)
            res += (" " + adj[i][j]);
        if (i + 1 < adj.length)
            res += "\n";
    }
    return res;
}

Anotácia @Override nám len hovorí, že prepisujeme metódu ToString(), ktorú jazyky už väčšinou obsahujú.

Prvý riadok nám len definuje premennú res (riešenie) ako String. for -cyklem prechádzame maticu a postupne ju vypisujeme. Ak sme na konci riadku, len vypíšeme nový riadok, aby výstupom bola pekná matice. Jednoduché, že?