Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G=(V,E) с исходной вершиной s; в котором веса всех ребер неотрицательны (w(u,v) ≥ 0 для всех (u,v) ÎE).
Предполагается, что граф задан с помощью списков смежных вершин.
В процессе работы алгоритма поддерживается множество S Í V, состоящее из вершин v, для которых d( s,v) уже найдено.
Алгоритм выбирает вершину uÎ V \ S с наименьшим d[u], добавляет u к множеству S и производит релаксацию всех ребер, выходящих из u, после чего цикл повторяется.
Вершины, не лежащие в S, хранятся в очереди Q с приоритетами, определяемыми значениями функции d.
DIJKSTRA (G, w, s)
1 INITIALIZE-SINGLE-SOURCE (G,s)
2 S ¬ Æ
3 Q¬ V[G]
4 whileQ ¹ Æ
5 do u¬ EXTRACT-MIN(Q)
6 S ¬ S È {u}
7 for (для) всех вершин vÎAdj[u]
8 do RELAX (u,v,w)
Поскольку алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути, он является жадным алгоритмом. Доказано, что в данном случае жадная стратегия дает правильный результат.