Page 65 - 4336

Крім того, для всіх i та m:

d m  0. (4.8)
,i i

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

величинами елементів матриці D , можуть бути визначені
,
аналогічно тому, як це робилося в алгоритмі Флойда-Уоршола.

Згідно з формулами (4.5)-(4.8), на кожному кроці 2

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

, матриці D , що знаходяться в m-му стовпчику та m-му рядку
матриці (формули (4.5), (4.6)), а потім усі інші елементи за

формулою (4.7) (крім елементів основної діагоналі матриці, що

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

В алгоритмі Данцига виконуються по суті ті ж самі операції,

що і в алгоритмі Флойда-Уоршола, тільки в іншому порядку.

Дійсно, рівняння (4.2), що використовується в алгоритмі Флойда-

Уоршола, просто збігається з рівнянням (4.7) алгоритму Данцига.

Рівняння (4.5) та (4.6), що використовується в алгоритмі Данцига,

просто m-1 раз повторюють рівняння (4.2) з алгоритму Флойда-

Уоршола. Таким чином, кожний із алгоритмів включають те саме

число операцій.

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

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

Розв'язок.

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

0 1 2 1

D 0  2 0 7  .
6 5 0 2

1  4 0

65