Алгоритм решения (алгоритм Дейкстры)

Алгоритм Дейкстры применим для неотрицательных элементов матрицы с и состоит из двух частей: прямого и обратного ходов. Прямой ход содержит начальное заполнение и итеративную процедуру. В процессе работы каждому узлу i приписывается, а затем изменяется некоторое число, называемое пометкой, которая может быть двух видов - постоянная L_i или временная I_i . Изменяться при этом могут только временные пометки. Присвоенные узлам постоянные пометки в дальнейшем изменяться не могут.

Начальное заполнение:

Источнику присвоить постоянную пометку 0. Остальным узлам i присвоить временные пометки, численно равные элементам csi матрицы обобщенной стоимости дуг из источника в узел i. Для узлов, не являющихся конечными для дуг, идущих из источника, временные пометки равны . Ls = 0; Ii = csi, i N, i s.

Начальное заполнение производится один раз перед итеративной процедурой, которая состоит не более чем из n -1 итерации (где n - число узлов сети) и продолжается до тех пор, пока сток не будет помечен постоянной пометкой. Каждая итерация выполняется по одному и тому же алгоритму и состоит из двух шагов.

Итерация:		Шаг 1:		Для всех узлов i с временными пометками Ii вычислить их новое значение Ii как наименьшее из старого значения пометки и суммы полученной на предыдущей итерации постоянной пометки Lj с обобщенной стоимостью дуги [ ji ]. Ii ’ =min {Ii; Lj + сji}; j: Lj = {Li} (3)
		Шаг 2:		Узлу, временная пометка которого является наименьшей из всех еще существующих временных пометок, присвоить постоянную пометку, численно равную этой временной. Lj = Ij; j: Ij = {Ii} (4) Если помеченным оказывается сток (j = r), прямой ход алгоритма Дейкстры закончен.

Величина постоянной пометки стока равна обобщенной стоимости неизвестной пока еще оптимальной цепи. Сама цепь определяется во второй части алгоритма Дейкстры и состоит из дуг, для каждой из которых разность между значениями постоянных пометок ее концевых узлов, равна длине (обобщенной стоимости) этой дуги. Иными словами, условие, при выполнении которого узлы i и j принадлежат кратчайшей цепи [ s,..., i, j,..., r ] может быть записано следующим образом:

L_j - L_i - c_ij = 0. (5)

Это соотношение можно использовать рекурсивно, двигаясь от узла r к узлу s.

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

Итеративная процедура состоит не более чем из n -1 итерации и продолжается до тех пор, пока источник не попадет в оптимальную цепь. Каждая итерация выполняется по одному и тому же алгоритму и состоит из двух шагов.

Итерация:		Шаг 1:		Для всех узлов i с постоянными пометками Li вычислить величину i = Lj - Li - cij, где Lj - постоянная пометка узла j, последним включенного в оптимальную цепь.
		Шаг 2:		Включить в оптимальную цепь узел, удовлетворяющий условию (5): i ’ = 0. Если это исток (i ’= s), обратный ход алгоритма Дейкстры закончен.

Совершенно аналогичным методом может быть решена задача о цепи максимальной длины, однако при этом в прямом ходе алгоритма Дейкстры в выражениях (3) и (4) необходимо min {...} заменить на max {...} (от тех же выражений) и в начальном заполнении прямого хода алгоритма Дейкстры вместо необходимо ввести - .

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