Grafové algoritmy – hledání minimální cesty

Dijkstrův algoritmus, Floyd–Warshallův algoritmus – principy algoritmů, složitost

Algoritmy pro hledání minimální cesty, jak jejich název napovídá, spočívají v nalezení nejkratší cesty mezi dvěma vrcholy grafu, tedy nalezení posloupnosti hran s nejnižším součtem vah.

Definice potřebných pojmů:

  • cesta - tah, ve kterém se neopakuje žádný vrchol
    • tah - sled, ve kterém se neopakuje žádná hrana
      • sled - posloupnost hran, které na sebe vzájemně navazují

Dijkstrův algoritmus

Algoritmus pro hledání nejkratší cesty v grafu, popsaný Edsgerem Dijkstrou je konečný algoritmus (pro konečný vstup se vždy dostane do konce), který funguje v grafech s kladně ohodnocenými hranami. V každém průchodu cyklem grafu se přidává k výsledku právě jeden vrchol, maximální počet průchodů je tedy roven počtu vrcholů. Jedná se o variaci na prohledávání do šířky.

Dijkstrův algoritmus umí jedním průchodem nalézt nejkratší cestu do všech vrcholů grafu, nikoliv pouze do jednoho.

Princip

Máme:

  • graf \( G \)
  • množinu vrcholů \( U \) grafu \( G \)
    • pro každý vrchol \( v \) z množiny \( V \) hodnotu \( d[v] \), která znamená nejkratší cestu k němu (známou v aktuálním cyklu)
      • počáteční vrchol \( s \) má \( d[s] = 0 \)
      • všechny ostatní vrcholy mají na začátku \( d[v] = \infty \)
    • množinu nenavštívených vrcholů \( N \)
    • množinu navštívených vrcholů \( Z \)
  • množinu hran \( H \) grafu \( G \)

Postup:

  1. vezmeme vrchol \( v \) z \( N \), který má nejnižší hodnotu \( d[v] \)
  2. pro každý vrchol \( u \), který je sousedem \( v \) a nepatří zatím do \( Z \) spočítáme jeho vzdálenost přes \( u \), a to takto: \( l = d[v] + m \), kde \( m \) je vzdálenost mezi \( v \) a \( u \) (váha hrany mezi nimi) a \( l \) výsledná vzdálenost vrcholu \( u \) od počátku
  3. porovnáme \( l \) s \( d[u] \) (tedy s aktuální vzdáleností \( u \) od počátku)
    • pokud je \( l \) nižší, nastavíme hodnotu \( d[u] \) na \( l \)
    • pokud je vyšší, neděláme nic
  4. předešlé kroky opakujeme, dokud není množina \( N \) prázdná

Výsledkem je, že ke každému vrcholu \( v \) máme vzdálenost od \( s \), tedy \( d[v] \) a rovněž odkaz na předešlý vrchol v cestě, tudíž jsme schopni ji zpětně zrekonstruovat.

Složitost

  • pří použití obyčejného pole k uložení vzdáleností (nejnižší hodnota se hledá klasickým procházením tohoto pole) je \( O(|U|^2 + |H|) \)
  • máme-li řídký graf (počet hran je mnohem menší než \( |U|^2 \)), můžeme pomocí ukládání do seznamu sousedů a hledání nejnižší vzdálenosti binární nebo Fibonacciho haldou dosáhnout složitosti \( O(|H| + |U| \cdot \log{|U|}) \)
  • \( |U| \) značí počet vrcholů a \( |H| \) počet hran grafu

Floyd–Warshallův algoritmus

Algoritmus poprvé popsaný Robertem Floydem a Stephenem Warshallem je schopný nalézt jedním průchodem nejkratší cestu mezi všemi dvojicemi vrcholů v grafu. Na rozdíl od Dijkstrova algoritmu podporuje i přítomnost hran s negativními vahami. Jeho výhodou je snadná implementace.

Princip

Máme:

  • graf \( G \)
  • matici délek \( D \)
    • její hodnota na pozici \( i \) a \( j \) odpovídá váze hrany mezi vrcholy \( i \) a \( j \)
      • z toho plyne, že na diagonále má samé nuly
      • není-li mezi vrcholy hrana, je na příslušné pozici \( \infty \)
    • lze říci, že obsahuje vzdálenosti uzlů, které jsou propojeny bez prostředníka

Postup:

Vytvoříme tři vnořené cykly s řídicími proměnnými \( i \), \( j \) a \( k \). Význam proměnných \( i \) a \( j \) odpovídá popisu výše (jedná se o indexy matice), \( k \) značí počet mezivrcholů, skrze které může propojovací cesta vést (vysvětleno dále). Všechny tři řídicí proměnné mají maximální hodnotu odpovídající řádu matice (počtu řádků či sloupců matice (vždy je čtvercová)).

V každé iteraci aplikujeme na aktuální hodnotu (na pozici \( i \), \( j \)) funkci \( f(i, j, k) \), která zjišťuje, zdali mezi vrcholy \( i \) a \( j \) neexistuje kratší cesta přes \( k \) mezivrcholů. Pokud ano, upraví danou hodnotu.

Jak se hodnota \( k \) (a samozřejmě i \( i \) a \( j \)) zvyšuje (iteracemi jejího cyklu), tak postupně dochází ke kontrole a případné úpravě všech hodnot v matici pro \( 0 \) mezivrcholů - počáteční stav, pro \( 1, 2, ..., d \), kde \( d \) je řád matice.

Složitost

Vzhledem k tomu, že se jedná o tři vnořené cykly, časová složitost algoritmu je \( O(|U|^3) \).

Zdroje