Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

5.4.2. А
ЛГОРИТМ 
Д
ЕЙКСТРЫ
 
Наиболее эффективный алгоритм поиска кратчайших путей в графах с 
неотрицательными весами ребер дал Эдсгер В. Дейкстра [19]. Этот алгоритм 
основан на том, что каждому узлу приписывается расстояние Dist от исход-
ного узла и признак возможности изменять это расстояние Visit, которые 
меняются в процессе работы алгоритма. Алгоритм основан на итерационном 
уточнении значений расстояний от исходных больших величин до конечных, 
равных длинам соответствующих кратчайших путей. Основная идея уточне-
ния основана на простой формуле Dist(x
i
) = Min(Dist(x
i
), Dist(p) + Ap
i
), 
геометрический смысл которой представлен на рис. 5.11. 
P
S
Xi
Api
Рис. 5.11. Геометрическая интерпретация идеи уточнения расстояния 
Если между вершинами p и x
i
нет ребра, то A
pi
= ∞ и Dist(x
i
) не меня-
ется. Если же между этими вершинами есть ребро и Dist(p) уже достигло 
минимального значения, то Dist(x
i
) также принимает минимальное значе-
ние. 
В начале работы алгоритма выделенным является только узел s. На ка-
ждом шаге алгоритма в число выделенных добавляется один узел, поэтому 
множество выделенных узлов постепенно расширяется и, в конце концов, 
выделенными оказываются все узлы. В процессе выполнения алгоритма для 
каждого выделенного узла в массиве расстояний хранится наименьшая длина 
пути от исходного узла. При этом известно, что минимальное значение дли-
ны достигается на пути, проходящем только через выделенные узлы. Нако-
нец, для каждого еще не выделенного узла в массиве расстояний хранится 
наименьшая длина пути, который проходит только через выделенные узлы. 
Выбор очередного узла для включения в число выделенных произво-
дится следующим образом. Среди всех невыделенных узлов выбирается узел 
с минимальным значением расстояния от исходной вершины. Путь, соответ-
ствующий этому расстоянию, для этого узла является кратчайшим, так как 
проходит только через выделенные узлы, обладающие таким же свойством. 
8 / 23

---

170 
Отметим, что это утверждение справедливо только при условии неотрица-
тельности весов ребер. 
После добавления очередного выделенного узла необходимо произве-
сти корректировку данных для невыделенных узлов. Достаточно при этом 
учесть лишь ребра, в которых новая вершина является последней, а это легко 
сделать, т. к. минимальная длина пути в новый узел уже известна. 
Если для хранения множества выделенных узлов задан массив логиче-
ского типа, то добавление одного узла к числу выделенных требует времени 
O(N). В процессе работы алгоритма элементы массива расстояний переходят 
из состояния «можно изменять» в состояние «менять нельзя». Вначале только 
у элемента Dist[s], имеющего значение 0, ставится пометка «менять нель-
зя», и на каждом шаге итерационного процесса такая пометка ставится еще у 
одного элемента. Процесс заканчивается, когда у всех элементов будет стоять 
пометка «менять нельзя», т. е. за (N 
− 1) шаг. 
Для реализации этого алгоритма уточним структуру, описывающую уз-
лы (листинг 5.30).