Пример решения. Рассмотрим работу алгоритма Дейкстры на примере сети, изображенной на рис

Рассмотрим работу алгоритма Дейкстры на примере сети, изображенной на рис. 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			r =4
Итерация:	Значения пометок

В обратном ходе алгоритма Дейкстры (см. рис. 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			Оптимальная цепь
Итерация:	Значения i
				[?, 4]
	-		-2	[?, 2,4]
			-	[1, 2, 4]

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