кладається з наступних кроків.
Крок 0 . вихідному вузлу (вузол 1) присвоюється мітка [0, -] . Вважаємо i=1.
Крок i . а) Обчислюються тимчасові мітки [ui + d ij, i] для всіх вузлів j, які можна досягти безпосередньо з вузла i і які не мають постійних міток. Якщо вузол j вже має позначку [uj, k], отриману від іншого вузла k, і якщо ui + d ij < uj, тоді мітка [uj, k] замінюється на [ui + d ij, i].) Якщо всі вузли мають постійні мітки, процес обчислень закінчується. В іншому випадку вибирається мітка [ur, s] з найменшим значенням відстані ur серед усіх тимчасових міток (якщо таких міток декілька, то вибір довільний). Вважаємо i=r і повторюємо крок i.
Приклад. На малюнку 2 показана транспортна мережа, що складається з п'яти міст (відстані між містами (у кілометрах) наведені біля відповідних дуг мережі). Необхідно знайти найкоротші відстані від міста 1 (вузол 1) до всіх інших чотирьох міст.
Рис. 2. Транспортна мережа
Крок 0 . Призначаємо вузлу 1 постійну позначку [0, -].
Крок 1 . З вузла 1 можна досягти вузлів 2 і 3. Обчислюємо мітки для цих вузлів, в результаті отримуємо наступну таблицю міток:
Вузол Мітка Статус мітки
[0, -] Постійна
[0 + 100, 1]=[100, 1] Тимчасова
[0 + 30, 1]=[30, 1] <-Тимчасова
Серед вузлів 2 і 3 вузол 3 має найменше значення відстані (u 3=30). Тому статус мітки цього вузла змінюється на «постійна».
Крок 2 . З вузла 3 (останнього вузла з постійною міткою) можна потрапити в вузли 4 і 5. Отримуємо наступний список вузлів:
Вузол Мітка Статус мітки
[0, -] Постійна
[100, 1] Тимчасова
[30, 1] Постійна
[30 + 10, 3]=[40, 3] <-Тимчасова
[30 + 60, 3]=[90, 3] Тимчасова
Тимчасовий статус мітки [40, 3] вузла 4 замінюється на постійний (u 4=40).
Крок 3 . З вузла 4 можна досягти вузлів 2 і 5. Після обчислення міток одержимо наступний їх список:
Вузол Мітка Статус мітки
[0, -] Постійна
[40 + 15, 4]=[55, 4] <-Тимчасова
[30 , 1] Постійна
[40 , 3] Постійна
[90, 3] або [40 + 50, 4]=[90, 4] Тимчасова
Тимчасова мітка [100, 1], отримана вузлом 2 на другому кроці, змінена на [55, 4]. Це вказує на те, що знайдено більш короткий шлях до цього вузла (що проходить через вузол 4). На третьому кроці вузол 5 отримує дві мітки з однаковим значенням відстані u 5=90.
Крок 4 . З вузла 2 можна перейти тільки у вузол 3, але він вже має постійну мітку, яку не можна змінити. Тому на даному кроці отримуємо такий же список міток, як і на попередньому кроці, але з єдиною зміною: мітка вузла 2 отримує статус постійною. З тимчасової...
