Office week BF - Easter
Tento týden až 80% sleva na e-learning MS Office!
80 % bodů zdarma díky naší Velikonoční akci!

Implementace algoritmu Floyd-Warshall - Nejkratší cesty

S teorií okolo hledání nejkratší cesty v grafu jsme se již setkali v lekci Hledání nejkratší cesty v grafu, kde také naleznete další teorii k problematice hledání nejkratší cesty v grafu.

V tomto článku se budeme věnovat samotné implementaci algoritmu Floyd-Warshall. Tento algoritmus se používá, pokud chceme mít někde uloženou matici vzdáleností mezi všemi vrcholy grafu a pomocí ní zjistit nejkratší cestu mezi jednotlivými vrcholy. V tom je ale potíž algoritmu. Jeho časová a hlavně paměťová složitost je O(n3). Jednoduše totiž projde všechny možné cesty mezi všemi dvojicemi vrcholů. Při milionu vrcholů je to už značná pálka... Ale na druhou stranu je algoritmus jednoduchý a napíšeme ho hned :)

Popis algoritmu

Pro ilustraci se ještě jednou podívejme na popis algoritmu. Mějme ohodnocený graf G, který máme uložený jako matici vzdáleností. Pokud nás tedy např. zajímá vzdálenost mezi vrcholy 1 a 2, zjistíme ji jako G[1][2]. A jak tedy najdeme nejkratší cesty mezi všemi možnými dvojicemi vrcholů v grafu? Budeme postupovat 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]

Pro každý vrchol v grafu najdeme druhý vrchol (tím máme dvojici) a k nim najdeme třetí vrchol (zkusíme si to přes něj zkrátit). Dále chceme říci, že pokud je cesta mezi dvěma vrcholy delší než cesta přes třetí vrchol, použijeme menší vzdálenost přes třetí vrchol. To je celá magie Floyd-Warshalla. Jelikož se vzdálenost hned přepíše v matici vzdáleností, bude nová zkratka použita i pro další průchody.

Podobný algoritmus provádíme běžně, např. pokud je někde zácpa a chceme se dostat do města A rychleji, vezmeme to přes nějaké město B a vyhneme se zdržení. Zde to jen přepisujeme do kódu.

Implementace

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Myslím, že víme, co chceme dělat. Pojďme algoritmus tedy přepsat do kódu.

Inicializace

Začneme inicializací:

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 matici a nekonečno. Připravíme si naši matici vzdáleností jako nové pole typu int. Parametr uzly označuje počet uzlů.

Pomocí for cyklů projedeme všechny dvojice uzlů i, j. Ty, které se rovnají, jsou 0, protože vzdálenost z nějakého vrcholu do toho samého vrcholu je 0. Ostatní hodnoty vzdáleností jsou nekonečno, protože ještě nemáme přidané ohodnocené hrany. nekonečno je tedy naše výchozí hodnota a označuje, že mezi vrcholy zatím není cesta.

Přidání hrany

Dále si přidáme metodu k přidání hrany do matice vzdáleností mezi všemi vrcholy v grafu. Jako parametry uvedeme mezi jaké vrcholy hranu vkládáme a jaká je mezi nimi vzdálenost (tedy jaká je váha hrany):

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

Vzdálenost mezi dvěma hranami přidáme pomocí minima z hodnoty adj[u][v] a váhy hrany (vzdálenosti). V matici jsou hodnoty uložené po inicializaci (tedy 0 nebo nekonečno). Pokud je zde 0, chceme ji zachovat. V případě nekonečna hodnotu přepíšeme na danou váhu hrany.

Samotné hledání

Postupme dále k již zmíněné trojici for cyklů, kterými projdeme naši matici:

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]);
            }
        }
    }
}

Pokud narazíme v matici vzdáleností na hranu, která má nějakou váhu, neboli vzdálenost mezi k a j je menší než nekonečno, tak potom zkusíme, zda je vzdálenost mezi k a j větší než vzdálenost mezi i k a i j. Co je to vlastně za podmínku?

Jde nám o to, zda je rychlejší přímá cesta mezi dvěma vrcholy, nebo je rychlejší jet přes třetí vrchol. A to je přesně to, co dělá testování nejkratší vzdálenosti. No a to je celý algoritmus. Je elegantní, jednoduchý, ale bohužel náročný na výpočet. Tři for cykly v sobě nám dají kubickou O() notaci.

Vidíme, že výsledek upravujeme přímo v matici vzdáleností.

Vypišme výsledek

Jelikož jsme už s algoritmem hotovi, tak si udělejme radost a ještě si udělejme po dobře odvedené práci hezký 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;
}

Anotace @Override nám jen říká, že přepisujeme metodu ToString(), kterou jazyky již většinou obsahují.

První řádek nám jen definuje proměnnou res (řešení) jako String. for-cyklem procházíme matici a postupně ji vypisujeme. Pokud jsme na konci řádku, jen vypíšeme nový řádek, aby výstupem byla pěkná matice. Jednoduché, že? :)


 

Stáhnout

Staženo 5x (4.06 kB)
Aplikace je včetně zdrojových kódů

 

 

Článek pro vás napsal Tricerator
Avatar
Jak se ti líbí článek?
Ještě nikdo nehodnotil, buď první!
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šechny články v sekci
Grafové algoritmy
Aktivity (2)

 

 

Komentáře

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.

 
Odpovědět
22.12.2019 13:27
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 1 zpráv z 1.