Page 154 - Bkhargava_-_Grokaem_algoritmy

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

Этот путь занимает 7 минут. А может, существует путь, который займет
меньше времени? Алгоритм Дейкстры состоит из четырех шагов:

1. Найти узел с наименьшей стоимостью (то есть узел, до которого можно
добраться за минимальное время).

2. Обновить стоимости соседей этого узла (вскоре я объясню, что имеется
в виду).
3. Повторять, пока это не будет сделано для всех узлов графа.

4. Вычислить итоговый путь.

Шаг 1: найти узел с наименьшей стоимостью. Вы стоите в самом начале
и думаете, куда направиться: к узлу А или к узлу В. Сколько времени по­
надобится, чтобы добраться до каждого из этих узлов?

6
::._' 1 /

До узла А вы будете добираться 6 минут, а до узла В - 2 минуты. Что каса-
ется остальных узлов, мы о них пока ничего не знаем. ЬРЕМЯ
ПEPE)(OJZ.A
Так как время достижения конечного узла остается не- УJЕЛ к УJЛУ
известным, мы считаем, что оно бесконечно (вскоре вы А cS
увидите почему.) Узел В - ближайший ... он находится в 2
всего в 2 минутах.
КОНЕЦ ()о

www.trk.kg