Relaxace

Zobecnění relaxace z Dijsktry nebo Jarníkova algoritmu

Tedy Dijkstra je speciální případ tohoto obecného algoritmu

Připouštíme obecné ohodnocení hran (klidně i záporné)

Místo otevřeného vrcholu s nejmenší hodnotou vybereme libovolný vrchol s konečným ohodnocením

• Relaxujeme jeho následníky
• Poté ho uzavřeme

Může se stát, že uzavřený vrchol bude znovu otevřen

Stavy mohou být tyto:

• Otevřený - byl relaxovaný a má relaxovat své následníky
• Uzavřený - po své relaxaci provedl relaxaci následníků