Ohodnocený orientovaný graf

  • Hledání nejkratší cesty v ohodnoceném grafu

  • Délka = ohodnocení hrany, značíme

    • Délka sledu je součet délek jeho hran

  • Vzdálenost = minimum z délek všech --cest, značíme

Zkracování sledů

Lemma (o zjednodušování sledů)

Pokud jsou délky hran kladné, pak pro každý -sled existuje -cesta stejné nebo menší délky.

Důkaz
  • Pokud sled není cestou, znamená to, že se v něm opakují vrcholy.
  • Označme tedy první vrchol (v pořadí od ), který se opakuje.
  • Část sledu mezi prvním a posledním výskytem vrcholu vystřihneme a získáme -sled stejné nebo menší délky.
  • Přitom ubyly nejméně 2 hrany, takže opakováním tohoto postupu časem dostaneme cestu.
    ../Attachments/Pasted image 20230126145152.png

Trojúhelníková nerovnost

Důsledek

Jsou-li délky hran kladné, platí pro vzdálenosti trojúhelníková nerovnost: pro libovolné
../Attachments/Pasted image 20230126145742.png

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 18. 3. 2025, 23:35