Dijkstra

  • Předpokládá kladné délky hran

  • Úprava BFS, ale místo rozdělování hran na několik jednotkových hran, nařídíme "budíky"

    • Ze správnosti BFS plyne, že i takovýto algoritmus je správný

  • = čas nastavený na budíku vrcholu, počáteční hodnota

  • Rozlišujeme 3 stavy vrcholů:

    • Nenalezený
    • Otevřený - už tiká budík
    • Uzavřený - budík už zazvonil

  • Pro každý vrchol kromě počátečního si pamatujeme předchůdce , abychom mohli nejkratší cesty zrekonstruovat

  • Využíváme prioritní frontu (případně nějakou minimovou haldu)

Relaxace vrcholů

Definice

Přepočítávání ohodnocení následníka vrcholu v Dijsktrově alg. (přeřizování budíků) budeme nazývat relaxace následníka vrcholu .

../Attachments/Pasted image 20230126152836.png

Složitost

  • Pokud jsou délky kladné, potom nad souvislým grafem o vrcholech běží v čase
    • Inicializace trvá
    • Každý vrchol uzavřeme nejvýše jednou
    • Vnějším cyklem projdeme nejvýše -krát
    • Pokaždé hledáme minimum až z ohodnocení, procházíme až následníků

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25