Page 157 - Bkhargava_-_Grokaem_algoritmy

156 Глава 7. Алгоритм Дейкстры

Последний шаг - вычисление итогового пути - откладывается до следую­
щего раздела. А пока я просто покажу, как выглядит итоговый путь.

Алгоритм поиска в ширину не найдет этот путь как кратчайший, потому
что он состоит из трех сегментов, а от начального узла до конечного можно
добраться всего за два сегмента.

КРНЧАКШИК ПУТЬ
С ПОИСКОМ 6 ШИРИНУ

В предыдущей главе мы использовали поиск в ширину для нахождения
кратчайшего пути между двумя точками. Тогда под «кратчайшим путем»
понимался путь с минимальным количеством сегментов. С другой стороны,
в алгоритме Дейкстры каждому сегменту присваивается число (вес), а ал­
горитм Дейкстры находит путь с наименьшим суммарным весом.

ЬJ&Е.ШЕ.ННЫК ГРАФ 1-\Е.&J&Е.ШЕ.ННЫК ГРАФ
(ПОИСК 6 ШИРИНУ)

www.trk.kg