Рішення прикладу 1

№ кроку	s							T
	[0]
	[0]
	[0]	[0]
	[0]	[0]
	[0]	[0]	[3]
	[0]	[0]	[3]
	[0]	[0]	[3]				[4]
	[0]	[0]	[3]				[4]
	[0]	[0]	[3]	[5]			[4]
	[0]	[0]	[3]	[5]			[4]
	[0]	[0]	[3]	[5]	[6]		[4]
	[0]	[0]	[3]	[5]	[6]		[4]
	[0]	[0]	[3]	[5]	[6]	[7]	[4]
	[0]	[0]	[3]	[5]	[6]	[7]	[4]
	[0]	[0]	[3]	[5]	[6]	[7]	[4]	[7]

Робота алгоритму починається з того, що джерелу s приписується постійна позначка [0], а вузлам - тимчасові позначки . Таким чином, та для .

Оскільки значення є мінімальним серед всіх тимчасових позначок, вузлу 1 приписується постійна позначка [0].

Вузли 2 та 3 безпосередньо зв'язані з вузлом 1, останнім з постійно позначених вузлів. Вони можуть отримати нові тимчасові позначки.

Відзначимо, що та . Тому вузлам 2 та 3 приписуються нові тимчасові позначки та відповідно.

З найменших тимчасових позначок обираємо постійну. Після порівняння , вузлу 2 приписується постійна позначка .

Поновлюємо тимчасові позначки. Вузли 3 і 6 безпосередньо зв'язані з вузлом 2. Крім того, та . Тому вузлам 3 та 6 приписуються нові тимчасові позначки та відповідно. Оскільки, вузол 6 стає позначеним постійно, тобто .

На даному кроку тимчасовими є позначки та . Останнім вузлом, якому була приписана постійна позначка, є вузол 6. Він безпосередньо пов'язаний лише з вузлом 4. Відзначимо, що . Отже, вузлу 4 приписується нова тимчасова позначка . Порівнюємо усі тимчасові позначки , вузлу 3 приписується постійна позначка . Аналогічно проведемо подальші обчислення.

Алгоритм закінчує роботу, коли вузлу приписується постійна позначка . Отже, довжина найкоротшого шляху з вузла в вузол дорівнює 7. Цей шлях складається з дуг, для кожної з яких різниця між значеннями постійних позначок її кінцевих вузлів дорівнює довжині цієї дуги. Цей факт можна використати при побудові зворотного ходу алгоритму Дейкстри, тобто при визначенні, через які саме вузли проходить найкоротший шлях.

Отже, якщо та - постійні позначки вузлів та відповідно, то умова, при виконанні якої ці вузли належать найкоротшому шляху, може бути записана так:

(1.8)

Співвідношення (1.8) можна використати рекурсивно, рухаючись від вузла до вузла s. Визначивши з матриці вартостей вузол, що безпосередньо передує в найкоротшому шляху, будемо повторювати дану процедуру, доки не досягнемо вузла s.

Матриця вартостей для графа, заданого на рис. 1.1, приведена в таблиці 1.2.

Таблиця 1.2

Матриця вартостей заданого графа.

С

Наприклад, визначимо найкоротший шлях між джерелом s та вузлом 5.

Позначка 5-го вузла - [7]. У стовпці 5-го вузла матриці вартостей знаходимо, що 5й вузол з'єднаний з третім і четвертим. Для цих вузлів виконуємо наступну операцію: від позначки 5-го вузла віднімаємо величину вартості відповідної дуги і, якщо отримана різність співпадає з позначкою для вузла, що розглядається, то цей вузол входить в найкоротший шлях.

В 5-й вузол можна попасти з 3-го або 4-го. Перевіримо, чи належить 3-й вузол найкоротшому шляху: .

Якби 3-й вузол належав найкоротшому шляху, то постійна позначка для цього вузла мала б бути: 7-4=3.

Але, як видно з таблиці 1.1 постійна позначка 3-го вузла дорівнює 5. Отже 3й вузол не належить найкоротшому шляху.

Аналогічна перевірка для 4-го вузла: , 7-1=6.

Це і є постійною позначкою для 4-го вузла. Отже він належить найкоротшому шляху.

Повторюємо цю процедуру для 4-го і наступних вузлів, як показано на рис.1.2.

1-2-6-4-5.