Bellman-Ford

  • Umí fungovat na grafech se zápornými hranami, ale bez záporných cyklů

  • Speciální případ relaxace

  • Namísto haldy (prioritní fronty) využijeme obyčejnou frontu

  • Tedy otevřený vrchol ke zpracování bude vždy nejstarší vrchol ve frontě

Fáze výpočtu (fáze běhu)

  • Nechť
  • Fáze otevření počátečního vrcholu , čili všech prvků množiny
  • je množina všech vrcholů, které byly relaxovány jako následníci vrcholů z množiny
  • Vytvoření množiny vrcholů se nazývá fáze
Pozorování
  • Pokud je relaxován uzavřený vrchol, je znovu otevřen.
  • Otevřený vrchol může být vícekrát relaxován, dříve než je vyjmut z fronty a uzavřen.
  • Během výpočtu může tedy daný vrchol postupně patřit do více .

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