Принцип работы алгоритма Дейкстры при обходе графа заключается в поиске кратчайшего пути от одной вершины графа до всех остальных. 12

Алгоритм начинается с установки начальной вершины и работы от этой точки. 1 Он работает по принципу «жадного» алгоритма, то есть на каждом шаге стремится минимизировать текущую общую стоимость пути. 1

Сначала инициализируются два множества: 1

1. Множество, содержащее уже обработанные вершины (изначально пустое). 1
2. Множество, содержащее все остальные вершины графа (изначально содержит все вершины графа). 1

Каждой вершине графа присваивается вес, который представляет минимальную известную стоимость пути от начальной вершины до данной. 1 Для начальной вершины этот вес равен 0, для всех остальных вершин — бесконечность. 1

На каждом шаге алгоритм: 1

• выбирает вершину из непосещённого множества с наименьшим весом; 1
• перемещает эту вершину в множество посещённых вершин; 1
• обновляет веса всех соседей выбранной вершины. 1 Вес соседа обновляется, если через выбранную вершину можно добраться до этого соседа с меньшей стоимостью. 1

Процесс продолжается, пока не будут посещены все вершины или пока не будет найден путь до конечной вершины (если она задана). 1

Алгоритм Дейкстры работает только для графов, у которых нет рёбер с отрицательным весом. 4