Принцип работы алгоритма Дейкстры при построении оптимального пути заключается в следующем: 13

1. Инициализация. 1 Создаются два множества: одно содержит уже обработанные вершины (изначально пустое), другое — все остальные вершины графа (изначально содержит все вершины графа). 1 Также каждой вершине графа присваивается вес, который представляет минимальную известную стоимость пути от начальной вершины до данной. 1 Для начальной вершины этот вес равен 0, для всех остальных вершин — бесконечность. 1
2. Выбор начальной вершины. 1 От неё будут отсчитываться пути. 2
3. Построение маршрута пошагово. 3 На каждом шаге алгоритм выбирает наименее отдалённую вершину и двигается к ней, затем к следующей — и так, пока не доберётся до цели. 3
4. Обновление весов. 1 Вес соседа обновляется, если через выбранную вершину можно добраться до этого соседа с меньшей стоимостью. 1
5. Завершение работы. 2 Когда непосещённые вершины заканчиваются, алгоритм прекращает работу. 2

Результат его действия — список кратчайших маршрутов до каждой точки из исходной. 2 Для каждого маршрута указана его длина. 2