Page 155 - Bkhargava_-_Grokaem_algoritmy

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

Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться
до всех соседей В при переходе по ребру из В.

УJЕЛ ЬPE.MJI ЧТО5ЬI .а.о-
А •5 5РАТЬСJI .а.о
УJЛА А, ТЕ.ПЕ.РЬ
в 2.
TPE.5YE.TCJI
конщ ":/- &С.Е.ГО S МИН

Ого, да мы обнаружили более короткий путь к узлу А! Раньше для перехода
к нему требовалось 6 минут.

А если идти через узел В, то существует путь, который занимает всего
5 минут!

Если вы нашли более короткий путь для соседа В, обновите его стоимость.
В данном случае мы нашли:

о Более короткий путь к А (сокращение с 6 минут до 5 минут).

о Более короткий путь к конечному узлу (сокращение от бесконечности
до 7 минут).

www.trk.kg