На этом шаге рассмотрим подробно программную реализацию алгоритма Дейкстры.
Первым действием нужно найти узел с наименьшей стоимостью (рис.1).
Рис.1. Первый шаг алгоритма Дейкстры. Поиск узла с наименьшей стоимостью
Вторым действием нужно получить стоимость и соседей этого узла (рис.2).
Рис.2. Второй шаг алгоритма Дейкстры. Стоимость и соседи узла
Третье действие направлено на перебор соседей узла (рис. 3).
Рис.3. Третий шаг алгоритма Дейкстры. Перебор соседей узла
У каждого узла имеется стоимость, которая определяет, сколько времени потребуется для достижения этого узла от начала. Здесь мы вычисляем, сколько времени потребуется для достижения узла А по пути Начало > Узел В > Узел А (вместо Начало > Узел А) (рис. 4).
Рис.4. Третий шаг алгоритма Дейкстры. Подсчет времени достижения узла
Сравним эти стоимости (рис. 5).
Рис.5. Третий шаг алгоритма Дейкстры. Сравнение стоимостей
Мы нашли более короткий путь к узлу А. Обновим стоимость (рис. 6).
Рис.6. Третий шаг алгоритма Дейкстры. Обновление стоимости
Новый путь проходит через узел В, поэтому В назначается новым родителем (рис.7).
Рис.7. Третий шаг алгоритма Дейкстры. Обновление родителей
Мы снова вернулись к началу цикла. Следующим соседом в цикле for является конечный узел (рис. 8).
Рис.8. Третий шаг алгоритма Дейкстры. Возврат к началу цикла
Сколько времени потребуется для достижения конечного узла, если идти через узел В (рис. 9)?
Рис.9. Третий шаг алгоритма Дейкстры. Расчет времени
Потребуется 7 минут. Предыдущая стоимость была бесконечной, а 7 минут определенно меньше бесконечности (рис. 10).
Рис.10. Третий шаг алгоритма Дейкстры. Обновление полученных результатов
Конечному узлу назначается новая стоимость и новый родитель (рис. 11).
Рис.11. Третий шаг алгоритма Дейкстры. Назначение новой стоимости и родителя
На следующем этапе узел помечается как обработанный (рис. 12).
Рис.12. Четвертый шаг алгоритма Дейкстры. Помечаем узел как обработанный
На последнем этапе нужно найти следующий узел для обработки (рис. 13).
Рис.13. Пятый шаг алгоритма Дейкстры. Определение очередного узла для обработки
Получим стоимость и соседей узла А (рис. 14).
Рис.14. Второй шаг алгоритма Дейкстры. Определение стоимости и соседей узла
У узла А всего один сосед: конечный узел (рис. 15).
Рис.15. Третий шаг алгоритма Дейкстры. Перебор соседей узла
Время достижения конечного узла составляет 7 минут. Сколько времени потребуется для достижения конечного узла, если идти через узел А (рис. 16)?
Рис.16. Третий шаг алгоритма Дейкстры. Подсчет времени достижения узла
Через узел А можно добраться быстрее! Обновим стоимость и родителя (рис. 17).
Рис.17. Третий шаг алгоритма Дейкстры. Обновление стоимости и родителей
После того как все узлы будут обработаны, алгоритм завершается.
На следующем шаге рассмотрим постановку задачи о максимальном потоке.
