Lekce 7 - Implementace algoritmu Floyd-Warshall - Nejkratší cesty

V minulé lekci, Implementace algoritmu Bellman-Ford - Nejkratší cesta grafu, jsme si ukázali implementaci algoritmu Bellman-Ford.

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(n³). 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

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?

V další lekci, Hledání kostry grafu, se podíváme na kombinatorický problém - hledání kostry grafu.

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.