Page 113 - 6197

i,
  j ), то із пункту i можна попасти в пункт k , а із пункту m
в пункт j . Тому
 
  2
j
i
L G 2   1  d  c ik   2  c , k  , m  .
0
mj

Рисунок 2.5 – Можливий маршрут із i в j

 
Найкоротший маршрут L G 2   1 буде у тому випадку, коли
матиме місце таке співвідношення:
 
  2
L G   1  d  min :c   2  min :c .
0
2
k j ik m i mj
Введемо таке позначення:
  2
  min :c   2  min :c .
ij ik mj
k j m i
(2.20)
Для обчислення  для нульового переходу необхідно
ij
знайти мінімальні елементи в рядку і стовпці, що
перетинаються (без врахування переходу   j і результати
i,
додати.

Знаходимо   max : і перехід i , j вибираємо як
i 0 0 j   2 ij 0 0
ij c  0
такий, що підлягає розгалуженню. Для знайденого переходу

i , j оцінка маршруту буде такою:
0 0
  d
L i 0 0   i 0 0 j . (2.21)

113