Minimální kostry a nejkratší cesty AG1

Algoritmus, který nalezne minimální kostru grafu. V každém kroku se vybere hrana s nejmenší vahou, která ne vytváří cyklus. Algoritmus pokračuje, dokud není nalezeno všech n-1 hran pro graf s n vrcholy.

Nejkratší cesta mezi dvěma vrcholy v grafu je cesta s minimální celkovou vahou hran.

Strom, který spojuje všechny vrcholy grafu s minimálním součtem vah všech hran.

Algoritmus, který nalezne minimální kostru grafu. V každém kroku se vybírá hrana s nejmenší vahou, která je incidentní s vrcholem v již vytvořeném stromu.

V grafu je to součet vah všech hran.

Strom v grafu je acyklický graf, který spojuje všechny vrcholy.

Počet hran incidentních s daným vrcholem.

Propojený graf, ve kterém není žádná cyklická cesta.

Sada vrcholů, které jsou propojeny hranami.

Cesta, která začíná a končí ve stejném vrcholu.

Hrana, která spojuje dva vrcholy.

Bod v grafu, kde se stýká několik hran.

Kdyby se změnila váha jedné hrany, minimální kostra by se mohla, ale nemusí změnit.

Topologické uspořádání vrcholů DAGu a procházení vrcholy v tomto pořadí. Při procházení vrcholů se relaxují hrany do vrcholů s menší momentální hodnotou.

Algoritmus vrátí nejkratší cestu, protože jednou zpracovaný vrchol nemůže již svou cestu změnit. Pokud by existovala kratší cesta, museli bychom se do nějakého vrcholu vracet, což by znamenalo existenci cyklu v DAGu.

Nelze jednoduše přičíst velkou konstantu k záporným hranám, protože to by penalizovalo levné cesty přes více hran a zneplatnilo by to celou optimalizaci.

Rozdělení každého vrcholu na dva nové vrcholy. Z vrcholu 1 povede hrana do vrcholu 2 s váhou daného vrcholu. Hrany do původního vrcholu povedou do vrcholu 1 a hrany z původního vrcholu povedou z vrcholu 2.

Po přidání n nových vrcholů a n hran se složitost algoritmu asymptoticky nezmění, protože je stále lineární v počtu vrcholů a hran.

Je-li váha hrany, která není součástí MST, zvýšena, nemá to na MST žádný vliv. Pokud je váha snížena, je hrana přidána do MST a pomocí DFS se najde cyklus, z něhož je odstraněna nejdražší hrana.

Zvýšení váhy hrany v MST vede k jejímu odstranění z MST. Pomocí BFS se určí, do kterých komponent se MST rozpadla. Následně se do MST přidá levnější hrana, která spojuje tyto komponenty.

Jarníkův a Kruskalův algoritmus je možné použít k nalezení MST i v případě grafu se zápornými hranami.

K záporným hranám lze přičíst konstantní číslo K, aby se staly nezápornými. MST se pak nalezne a od váhy se odečte (|V|-1) * K pro získání váhy původní MST.

UnionFind s „keříky“ je struktura používaná v Kruskalově algoritmu k efektivnímu spojování vrcholů a ověřování, zda tvoří cyklus.

Dijkstrův algoritmus je algoritmus pro nalezení nejkratších cest v grafu, který využívá heuristiku pro nalezení vždy nejlevnějšího vrcholu

Bellman-Fordův algoritmus je algoritmus pro nalezení nejkratších cest v grafu, který dokáže zpracovat i grafy se zápornými cykly.

Simple Bellman-Ford je varianta Bellman-Fordova algoritmu, která opakovaně prochází všechny hrany a aktualizuje vzdálenosti do vrcholů.

Je požadováno najít takový graf o n vrcholech, ve kterém existují 2Ω(𝑛) nejkratších cest mezi dvěma danými vrcholy.

Graf s exponenciálním počtem nejkratších cest mezi dvěma vrcholy může mít formu sítě o n vrcholech, kde je každá vrchol připojena k ostatním pomocí hran o stejných váhách, čímž se vytvoří mnoho stejných nejkratších cest.

MST algoritmy, jako jsou Jarníkův a Kruskalův, se dají použít i na grafy se zápornými hranami, protože srovnávají pouze relativní pořadí vah. Přidání konstanty K k záporným hranám tento princip nezmění, ale je potřeba upravit výslednou váhu MST o (|V|-1) * K.

UnionFind s „keříky“ je datová struktura efektivní jak pro zjišťování, zda patří dva vrcholy do stejné množiny (komponenty), tak pro rychlé spojování těchto množin. Používá se v Kruskalově algoritmu k vyloučení tvorby cyklů v MST.

Dijkstrův algoritmus je nenasytný algoritmus, protože vždy vybírá vrchol s nejmenší vzdáleností od zdroje. Tento algoritmus využívá heuristiku, která často vede k efektivnímu nalezení nejkratších cest, ale ne vždy zaručuje optimální řešení.

Simple Bellman-Fordův algoritmus provádí iterace přes všechny hrany a pro každou kontroluje, zda by aktualizace vzdálenosti do cílového vrcholu vedla k dosažení kratší cesty. V případě detekce záporného cyklu algoritmus tento cyklus v detekuje.

Exponenciální počet nejkratších cest mezi dvěma vrcholy je možný v grafech, které obsahují mnoho vrcholů s relativně podobnými vzdálenostmi od zdroje. Například síť o n vrcholech, kde je každá vrchol spojena s ostatními hranami o stejné váze, má exponenciální počet stejných nejkratších cest.