Наприкінці цього кроку система може перебувати в одному з трьох станів (вершин): 5, 6 й 7. У стан 5 можна потрапити по дугах і (зі станів 2 й 3 відповідно). Тоді для стану 5умовний оптимальний розв’язок знаходиться так:
,
– тобто, у вершину 5 найбільш вигідно можна потрапити з вершини 3.
У таблиці ці розрахунки відображаються таким чином:
d | 2+10=12 | |||||
f | 5+5=10 |
Для станів 6 і 7 співвідношення (2) мають вигляд:
,
– тобто, у вершину 6 найбільш вигідно можна потрапити з вершини 2.
,.
Отже, частина таблиці, що відповідає етапу 2:
d | 2+10=12 | |||||
f | 5+5=10 | |||||
e | 2+12=14 | |||||
g | 5+10=15 | |||||
i | 3+15=18 | |||||
h | 5+7=12 | |||||
j | 3+13=16 |
Аналогічні дії виконуємо на кроках 3 і 4 .
Повний процес розв’язання задачі наведений у таблиці 2:
Таблиця 2
Крок | Можливі стани наприкінці кроку (вершини ) | Варіанти розв’язків (управлінь) (попередня вершина) | Вартість розв’язку | Умовний оптимальний розв’язок | ||
Вхідна дуга | Попередня вершина | |||||
a | 0+2=2 | 1 | ||||
3 | b | 0+5=5 | ||||
c | 0+3=3 | |||||
d | 2+10=12 | |||||
f | 5+5=10 | |||||
e | 2+12=14 | |||||
g | 5+10=15 | |||||
i | 3+15=18 | |||||
7 | h | 5+7=12 | 3 | |||
j | 3+13=16 | |||||
k | 10+7=17 | 5,6 | ||||
m | 14+3=17 | |||||
p | 12+7=19 | |||||
9 | l | 10+5=15 | 7 | |||
n | 14+4=18 | |||||
q | 12+1=13 | |||||
10 | r | 17+1=18 | 9 | |||
s | 13+4=17 |
Порядок формування відповіді показано стрілками:
9→10
7→9→10
3→7→9→10
1→3→7→9→10
Відповідь: найкоротший шлях 1-3-7-9-10, довжина шляху 17.