Santa Claus — 2022-04-07 15:31 (273 days ago) — edit — reply
Upravíme Dijkstru takto: Prioritní frontu implementujeme jako pole délky $k$, které jako každý prvek bude mít přihrádku na vrcholy. Každá přihrádka bude oboustraně spojový seznam. Abychom pole nemuseli neustále posouvat, použijeme cyklickou implementaci. Budeme si udržovat pointer na aktuálně zpracovávaný vrchol, ten má nejmenší ohodnocení a všechny vrcholy tedy mají větší ohodnocení, ale maximálně o k větší, tedy se vejdou do pole. Nalezení dalšího vrcholu k relaxaci pouze projdeme pole od našeho ukazatele, což je maximálně k kroků, a pak vytáhneme první z přihrádky v konstantním čase. Abychom mohli v konstantním čase provést operaci decrease, máme každý vrchol uložený v oboustraně spojovém seznamu a každý vrchol si také bude pamatovat odkaz na svou reprezentaci v tomto seznamu a číslo své přihrádky. Při decrease se pak jednoduše v konstantním čase odebere z přihrádky (změní odkazy předchozího a následující prvku ve spojáku) a v konstantním čase se přidá do jiné přihrádky (tu nalezne díky pole v konstantním čase). Časová složitost je tedy ta, která byla požadovaná.