Виділимо всі можливі стани, які можуть мати місце наприкінці кроку 1, тобто визначимо множину : . Для вершин знайдемо умовні оптимальні розв’язки , і відповідно. Тут – довжина найкоротшого шляху на кроці 1 (на кроках від 1-го до (1)-го включно), за умови, що наприкінці цього кроку система перебуває в стані (вершині) 2. Аналогічно визначаються й . Відповідно до виразу (2) отримаємо:
;
;
.
| У цьому випадку, у кожну вершину, що аналізується, входить тільки по одній дузі. Тому мінімум не шукається. У кожному випадку умовний оптимальний розв’язок відповідає переходу з вершини 1 (=1). Така ситуація завжди має місце, якщо в слої є тільки одна вершина (у нас – вершина 1). |
Таблиця заповнюється таким чином:
Крок | Можливі стани наприкінці кроку (вершини ) | Варіанти розв’язків (управлінь) (попередня вершина) | Вартість розв’язку | Умовний оптимальний розв’язок | ||
Вхідна дуга | Попередня вершина | |||||
a | 0+2=2 | |||||
b | 0+5=5 | |||||
c | 0+3=3 |
У стовпчику вказується вершина , перехід з якої у вершину забезпечує мінімум виразу (2). У стовпчику f* вказується значення цього мінімуму – довжина найкоротшого шляху від вершини 1 до вершини .