На этом шаге продолжим знакомство с алгоритмом Дейкстры.
Рассмотрим шаги алгоритма более подробно.
Шаг 1: найти узел с наименьшей стоимостью.
Вы стоите в самом начале и думаете, куда направиться: к узлу А или к узлу В. Сколько времени понадобится, чтобы добраться до каждого из этих узлов?
До узла А вы будете добираться 6 минут, а до узла В - 2 минуты . Что касается остальных узлов, мы о них пока ничего не знаем.
Так как время достижения конечного узла остается неизвестным, мы считаем, что оно бесконечно. Узел В - ближайший он находится всего в 2 минутах.
Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех соседей В при переходе по ребру из В.
Мы обнаружили более короткий путь к узлу А! Раньше для перехода к нему требовалось 6 минут. А если идти через узел В, то существует путь, который занимает всего 5 минут! Если вы нашли более короткий путь для соседа В, обновите его стоимость. В данном случае мы нашли:
- Более короткий путь к А (сокращение с 6 минут до 5 минут).
- Более короткий путь к конечному узлу (сокращение от бесконечности до 7 минут).
На следующем шаге завершим рассмотрение пошагововго выполнения алгоритма Дейкстры.
