Page 153 - Bkhargava_-_Grokaem_algoritmy

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

сегментов (три сегмента). Но предположим, с каждым сегментом связыва­
ется продолжительность перемещения. И тогда выясняется, что существует
и более быстрый путь.

В предыдущей главе рассматривался поиск в ширину. Этот алгоритм нахо­
дит путь с минимальным количеством сегментов (граф на первом рисунке).
А если вы захотите найти самый быстрый путь (второй граф)? Быстрее
всего это делается при помощи другого алгоритма, который называется
алгоритмом Дейкстры.

Работа с алгоритмом Дейкстры

Посмотрим, как этот алгоритм работает с графом.

Каждому ребру назначается время перемещения в минутах. Алгоритм
Дейкстры используется для поиска пути от начальной точки к конечной
за кратчайшее возможное время.
Применив к этому графу поиск в ширину, вы получите следующий крат­
чайший путь.

www.trk.kg