Ітераційна процедура

Для даного вузла через будемо позначати оцінку довжини найкоротшого шляху з джерела s у вузол . Якщо ця оцінка не може бути поліпшена, то відповідне значення ми назвемо постійною позначкою і будемо позначати її символом [ ]. У протилежному випадку, назвемо його тимчасовою позначкою. Спочатку процедури постійна позначка приписується лише джерелу. Кожна інша позначка є тимчасовою і її величина дорівнює довжині дуги, що веде з джерела до відповідного вузла:

.

Для визначення найближчого до джерела вузла оберемо тимчасову позначку з мінімальним значенням та оголосимо її постійною позначкою:

[ ] = min .

Після цього до тих пір, доки стоку не буде приписана постійна позначка, необхідно виконати наступні дві процедури:

1. Розглянути вузли, що залишилися з тимчасовою позначкою. Порівняти величину кожної тимчасової позначки із сумою величини останньої з постійних позначок і довжини дуги, що веде з відповідного постійно позначеного вузла у вузол, що розглядається. Мінімальна з цих двох величин визначається як нова тимчасова позначка вузла.

2. Серед тимчасових позначок обрати ту, значення якої мінімальне, і оголосити її постійною позначкою. Якщо при цьому постійна позначка приписується вузлу , то алгоритм завершує роботу. У протилежному випадку перейти до кроку 1.

Цю процедуру можна оформити у вигляді таблиці розв’язання, в якій стовпці відповідають вузлам мережі, рядки - крокам ітеративного процесу, а її елементи - постійним та тимчасовим позначкам (див. Приклад 1).

Приклад 1. Знайти найкоротші шляхи з першого вузла до решти вузлів в мережі, граф якої приведено на рис. 1.1. Будемо вважати, що джерелом в мережі є вузол 1, а стоком – вузол 5.

Таблиця 1.1