Nalezení minimálních cest v grafu

Minimální cesty

Minimální cesta (nejkratší cesta) mezi dvěma vrcholy $s$ a $t$ v ohodnoceném grafu je taková posloupnost hran, která:

• začíná ve zdrojovém vrcholu $s$,
• končí v cílovém vrcholu $t$,
• a její celková váha (součet vah hran) je minimální mezi všemi možnými cestami z $s$ do $t$.

Ve speciálním případě, kdy všechny hrany mají jednotkovou váhu (například neohodnocený graf), je minimální cesta tou, která obsahuje nejmenší počet hran.

Význam algoritmů pro hledání nejkratších cest

Hledání minimálních cest má zásadní význam v celé řadě oblastí:

• Síťové směrování – výběr nejefektivnější trasy v počítačových nebo dopravních sítích.
• Logistika a navigace – výpočet tras s minimálními náklady nebo časy.
• Plánování úloh – například optimalizace v grafu závislostí.

Pro tyto úlohy existuje několik algoritmů, z nichž nejznámější je Dijkstrův algoritmus.

Dijkstrův algoritmus

Dijkstrův algoritmus řeší problém nalezení nejkratší cesty ze zdrojového vrcholu $s$ do všech ostatních vrcholů v grafu s nezáporným ohodnocením hran.

Princip

• Postupně rozšiřuje množinu vrcholů, pro které je známa jejich nejkratší vzdálenost od zdroje.
• V každém kroku vybere uzel s aktuálně nejmenší známou vzdáleností, a aktualizuje vzdálenosti do sousedů (tzv. relaxace hran).

Pseudokód

funkce Dijkstra(G, s):
    pro každý vrchol v v G:
        vzdálenost[v] := ∞
        předchůdce[v] := nedefinován
    vzdálenost[s] := 0
    Q := prioritní fronta všech vrcholů v G s klíčem vzdálenost

    dokud není Q prázdná:
        u := vrchol v Q s nejmenší hodnotou vzdálenost[u]
        odeber u z Q

        pro každého souseda v vrcholu u:
            alternativa := vzdálenost[u] + váha(u, v)
            pokud alternativa < vzdálenost[v]:
                vzdálenost[v] := alternativa
                předchůdce[v] := u
                aktualizuj prioritu vrcholu v v Q

Výstup

Po skončení algoritmu:

• dist[v] obsahuje minimální vzdálenost z s do v,
• prev[v] umožňuje zpětně rekonstruovat cestu.

Časová složitost

Závisí na použité datové struktuře:

• Bez haldy: $\mathcal{O}(V^2)$
• Binární halda: $\mathcal{O}((V+E)\log V)$

Omezení

Algoritmus nefunguje korektně pro grafy s negativními vahami hran. Pro takové případy je vhodné použít například Bellman-Fordův algoritmus.