Алгоритм Дейкстры для поиска кратчайшего пути в графе работает пошагово: 2

1. Инициализация. 2 Метка самой начальной вершины полагается равной 0, метки остальных вершин — бесконечности. 3 Это отражает то, что расстояния от начальной вершины до других вершин пока неизвестны. 3 Все вершины графа помечаются как непосещённые. 3
2. Первый шаг. 2 Выбирается ещё не посещённая вершина с самой маленькой меткой относительно исходной — то есть такая, которая находится ближе всех. 2 На первом шаге это одна из соседних вершин — та, которая соединена с исходной самым «маленьким» ребром. 2
3. Дальнейшие шаги. 2 Для выбранной точки нужно осмотреть соседей и записать длину пути до них с учётом пройденного пути. 2 А потом выбрать ближнюю точку. 2 При этом нужно учитывать точки, которые уже использовались в прошлый раз. 2 Если они дают более «выгодный» путь, лучше воспользоваться ими. 2 Вершину отмечают посещённой. 2
4. Повторение шагов. 2 Шаги повторяются, пока на графе есть непосещённые точки. 2 Если вершину не посетили, она не участвует в расчётах. 2 Если после её «открытия» появился новый, более короткий путь к какой-либо точке, то минимальное расстояние для неё перезаписывается. 2
5. Завершение алгоритма. 2 Когда непосещённые вершины заканчиваются, алгоритм прекращает работу. 2 Результат его действия — список кратчайших маршрутов до каждой точки из исходной. 2 Для каждого маршрута указана его длина. 2

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