Грокаем а Иллюстрированное пособие для программистов и любопытствующих

Ч МИН



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

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

Ш
аг 1: найти узел с наименьшей стоимостью. Вы стоите в самом начале и думаете, куда направиться: к узлу А или к узлу В. Сколько времени по­надобится, чтобы добраться до каждого из этих узлов?
До узла А вы будете добираться 6 минут, а до узла В — 2 минуты. Что каса­ется остальных узлов, мы о них пока ничего не знаем. ьремл
ПЕРЕХОДА
Т

А	б
В	2.
КОНЕЦ	Сх>

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