Office week Slevový týden - Květen
Pouze tento týden sleva až 80 % na e-learning týkající se MS Office
30 % bodů zdarma na online výuku díky naší Slevové akci!

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

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

Tento výukový obsah pomáhajú rozvíjať nasledujúce firmy, ktoré možno hľadajú práve teba!

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? :)


 

Stiahnuť

Stiahnuté 6x (4.06 kB)
Aplikácia je vrátane zdrojových kódov

 

 

Článok pre vás napísal Tricerator
Avatar
Ako sa ti páči článok?
Ešte nikto nehodnotil, buď prvý!
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Všetky články v sekcii
Grafové algoritmy
Aktivity (1)

 

 

Komentáre

Avatar
lastp
Redaktor
Avatar
lastp:22.12.2019 13:27

Tento algoritmus je jednoduchý, ale kvůli časové složitosti n3 je vhodný pouze pro obecné grafy s velkým množstvím hran. Na běžné grafy (silniční síť a podobně) je rychlejší n-krát spustit Dijkstrův algoritmus.
Paměťová složitost je n2.

 
Odpovedať
22.12.2019 13:27
Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 1 správy z 1.