Алгоритм Дейкстры

 

 

Формулировка задачи. Имеется граф. Некоторая его вершина обозначена как вершина 1. Необходимо найти минимальные  пути от вершины 1 до каждой из вершин графа. Минимальным путём будем называть путь с минимальной суммой цен вдоль пути. Ценой назовем неотрицательное число являющееся весом ребра.

 

Идея алгоритма. Идея основывается на следующем очевидном утверждении: Пусть построен минимальный путь из вершины A в вершину B. И пусть вершина B связана с некоторым количеством вершин i_.. Обозначим через C_i – цену пути из вершины B в вершину i. Выберем из C_i минимальную величину. Тогда минимальное продолжение пути из точки B пойдёт через выбранную величину.

Это утверждение действительно не требует доказательства. И из него вытекает очень  серьёзное следствие. Пусть есть множество вершин через которые уже проходят минимальные пути. Такое множество гарантированно есть, это вершина 1. Утверждение сформулированное выше даёт возможность добавлять к уже существующему множеству вершин (будем далее называть их выделенными) еще одну вершину, а так как в графе количество вершин конечно, то за конечное количество  шагов все вершины графа окажутся выделенными, а это и будет решением.

Сущность алгоритма Дейкстры и заключается в процедуре добавления еще одной вершины к множеству выделенных. Эта процедура состоит из двух шагов:

 

1.    Строим множество вершин инцидентных выделенным и находим среди их вершину с наименьшей ценой. Найденная вершина добавляется в множество выделенных.

2.    Строим множество вершин инцидентных выделенным и определяем для них новые цены. Новая цена вершины это минимальная цена пути от множества выделенных вершин до данной вершины. Строится новая цена так:

a.    Для невыделенной вершины во множестве выделенных определяется подмножество вершин инцидентных данной.

b.    Для каждой вершины выделенной подмножества определяется цена пути до данной.

c.    Определяется минимальная цена. Эта цена и становится ценой вершины.

 

Обратите внимание, что алгоритм работает с двумя типами цен: ценой ребра и ценой вершины. Цены ребер являются постоянной величиной. Цены же вершин постоянно пересчитываются. Смысл этих цен различен. Цена ребра это цена перехода из вершины в вершину соединённую этим ребром. А цена вершины это цена минимального пути.

Ещё одно важное замечание касается пересчета предварительных цен. Фактически, есть смысл пересчитывать предварительные цены только для тех вершин которые связаны с вершиной добавленной во множество выделенных на последнем шаге, так как для других вершин нет причин изменения предварительной цены.

 

 

 

Алгоритм

 

§      Множество выделенных вершин = исходная вершина

§      Пока есть невыделенные вершины выполнять

o     Для каждой вершины инцидентной ПОСЛЕДНЕЙ ВЫДЕЛЕННОЙ рассчитать предварительную цену как минимальную из уже имеющейся и цены полученной с учетом пути от ПОСЛЕДНЕЙ ВЫДЕЛЕННОЙ до данной.

o     Среди множества вершин для которых определена предварительная цена найти вершину с минимальным значением предварительной цены.

o     Найденную вершину занести в множество выделенных вершин.