Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

6.4. Legrövidebb utak

6.4. Legrövidebb utak

A csúcs legrövidebb út távolsága -től legyen , amelyet az -ből -be vezető egyes utak élszámáinak minimumaként definiálunk, ha van ilyen út, és , ha nem vezet út -ből -be.

6.25. Definíció. Egy hosszúságú -ből -be vezető utat és közötti legrövidebb útnak nevezzük.

6.26. Lemma. Legyen irányított vagy irányítatlan gráf és tetszőleges csúcs. Ekkor bármely élre:

Bizonyítás. Ha elérhető -ből, akkor is. Ebben az esetben, az -ből -be vezető legrövidebb út nem lehet hosszabb, mint ha az -ből -ba vezető legrövidebb utat kiegészítjük az éllel, így az egyenlőtlenség teljesül. Ha nem érhető el -ből, akkor , ezért az egyenlőtlenség biztosan igaz.