3. Пример решения

Р ассмотрим работу алгоритма Дейкстры на примере сети, изображенной на рис. 8. Узел s1 здесь является источником, r4 - стоком, а числа c_ij, приписанные дугам, соответствуют их длине или обобщенной стоимости. Матрица обобщенной стоимости этой сети имеет вид:

C  ;

Работа алгоритма (см. рис. 9) начинается с того, что источнику приписывается постоянная пометка I₁  0, а узлам j  2,3,4 присваиваются временные пометки I_j  . Таким образом производится начальное заполнение. В дальнейшем производится итеративная процедура. Первая итерация: на первом шаге вычисляются новые временные пометки всех узлов (2, 3, 4), не имеющих постоянных пометок:

I₂’ min {I₂, L₁  c₁₂}  min { , 0  3}  3,

I₃’ min {I₃, L₁  c₁₃}  min { , 0 2}  2,

I₄’ min {I₄, L₁  c₁₄}  min { , 0  }  .

На втором шаге узлу 3, временная пометка которого наименьшая из полученных, присваивается постоянная пометка L₃  I₃’  2.

Вторая итерация: на первом шаге вычисляются новые временные пометки узлов 2, 4, не имеющих постоянных пометок:

I₂’ min {I₂, L₃  c₃₂}  min {3,2  }  3,

I₄’ min {I₄, L₃  c₃₄}  min { , 2  7}  9.

На втором шаге узлу 2, временная пометка которого наименьшая из полученных, присваивается постоянная пометка L₂ I₂’  3.

Третья итерация: на первом шаге вычисляется новая временная пометка узла 4, не имеющего постоянной пометки:

I₄’ min {I₄, L₂  с₂₄}  min {9,3  4}  7.

На втором шаге узлу 4, временная пометка которого наименьшая (и единственная) из полученных, присваивается постоянная пометка L₄  I₄’  7. Так как помеченным оказался сток 4  r, прямой ход алгоритма Дейкстры закончен.

Г рафическая демонстрация этого решения приведена на рис. 9; табличное решение - в табл. 1.

Таблица 1: Прямой ход алгоритма Дейкстры

Узел i:	s1	2	3	r4
Итерация:	Значения пометок
0	0
1		3	2
2		3		9
3				7

В обратном ходе алгоритма Дейкстры (см. рис. 10) участвуют все 4 узла. После исходного заполнения оптимальная цепь имеет вид [?, 4]. Первая итерация: на первом шаге вычисляются величины:

₁  L₄ - L₁ - c₁₄  7 - 0 -  - ,

₂  L₄ - L₂ - c₂₄  7 - 3 - 4  0,

₃  L₄ - L₃ - c₃₄  7 - 2 - 7  - 2.

На втором шаге узел 2, для которого ₂  0, включается в оптимальную цепь [?, 2, 4].

Вторая итерация: на первом шаге вычисляются величины:

₁  L₂ - L₁ - c₁₂  3 - 0 - 3  0, ₃  L₂ - L₃ - c₃₂  3 - 2 -  - .

На втором шаге узел 2, для которого ₁  0 включается в оптимальную цепь [1, 2, 4]. Так как это источник (1  s), обратный ход алгоритма Дейкстры закончен.

Графическая демонстрация этого решения приведена на рис. 10; табличное решение - в табл. 2.

Таблица 2: Обратный ход алгоритма Дейкстры

Узел i:	s1	2	3	Оптимальная цепь
Итерация:	Значения i
0				[?, 4]
1	-	0	-2	[?, 2,4]
2	0		-	[1, 2, 4]

Таким образом, с использованием алгоритма Дейкстры решена задача поиска кратчайшей цепи (цепи наименьшей обобщенной стоимости) для сети G (см. рис. 8). Оптимальная цепь: [1, 2, 4], ее длина 7. Оптимальный поток F_min в сети G: F_min  {f₁₂  1; f₁₃  0; f₂₃  0; f₂₄  1; f₃₄  0}.