Page 46 - 4387

0
m
d m , j = min { d m ,i + d i m − 1 } ( = 2 , 1 ,...,m − ) 1 , (6.1)
j
, j
= i 2 , 1 ,..., − 1
m
i
m
d i m = min { d i m 1 − + d 0 ,m } ( = 2 , 1 ,..., − ) 1 , (6.2)
,m
j
, j
2 , 1 = j ,...,m 1 −
m
m
d i m = min { d i m + d m , j ;d i m − 1 } ,( ji = 2 , 1 ,..., − ) 1 . (6.3)
, j
, j
,m
Крім того, для всіх i та m:
d m = 0. (6.4)
,i i

Найкоротші шляхи, довжини яких визначаються

величинами елементів матриці , можуть бути визначені

,
аналогічно тому, як це робилося в алгоритмі Флойда-Уоршола.
Згідно з формулами (6.1)-(6.4), на кожному кроці 2

алгоритму спочатку необхідно обчислювати значення елементів

матриці , що знаходяться в m-му стовпчику та m-му рядку

,
матриці (формули (6.1), (6.2)), а потім усі інші елементи за
формулою (6.3) (крім елементів основної діагоналі матриці, що

завжди рівні 0).

Приклад 6.1. Застосувати алгоритм Данцига до графа,

наведеного в прикладі 5.1 (рис. 5.1).

Розв'язок.

Крок 1. Матриця є наступною:
0
0 1 2 1

D 0 = 2 0 7 ∞ .
6 5 0 2

1 ∞ 4 0

Крок 2. m=1. Очевидно, що матриця буде наступною:
1

D 1 = d 1 1 , 1 = 0.

45