Схема алгоритму зворотної прогонки (АЗП) по дугах, що входять

1. Покласти ; .

( - допоміжний масив. У ньому будемо зберігати поточну довжину найкоротшого шляху від всіх вершин не останнього слою. Початкове значення цієї довжини вважаємо рівним ).

2. Планування кроку

2.1 Виділити всі можливі стани, які можуть мати місце наприкінці кроку : всі

2.2. Для кожного стану виконати наступне:

По кожній дузі (k,s), що входить у вершину знайти

2.3 Вважаємо

3. j=j – 1. Якщо j= 0, то перейти до пункту 4, інакше – перейти до пункту 2.

4. Формування оптимального розв’язку.

Процес розв’язку ЗЗНШ АЗП по дугах, що входять, проілюстрований на рис. 16.

Рис. 16

У прямокутниках вказані значення, що послідовно принімалися величинами .