Page 64 - 4336

вершин графа, а другою частиною – найкоротшу дугу, що веде з

вершини j у вершину m (звичайно, слід розглядати тільки такі

вершини j, для яких існує хоча б одна дуга, що веде з j у m).

Аналогічно, найкоротший шлях з вершини m у вершину i, у

якому допускається використання в якості проміжних тільки m

перших вершин графа, повинен мати своєю першою частиною

найкоротшу дугу, що веде з вершини m у деяку вершину j (j<m), а

другою частиною – найкоротший шлях з вершини j в вершину i,

який допускає використання в якості проміжних тільки (m-1)

перших вершин (звичайно, слід розглядати тільки такі вершини j,

для яких існує хоча б одна дуга, що веде з m у j). Нарешті,

відзначимо, що величини , повинні бути рівними нулю.
З урахуванням наведених міркувань, опишемо алгоритм

Данцига.

Крок 1. Занумерувати вершини вихідного графа цілими

числами від 1 до N. Сформувати матрицю D , (розмірністю N×N),

кожний елемент якої визначає довжину найкоротшої дуги, що
,
веде з вершини i у вершину j. При відсутності такої дуги

присвоїти ∞.
,

Крок 2. Через D позначається матриця розмірністю m×m з

елементами , m=1, 2, ..., N. Послідовно визначити елементи
,

матриці D за елементами матриці D для m, що приймає

значення 1, 2, ..., N:

0
m
d m , j  min  d m ,i  d i m  1  ( j 2 , 1 ,...,m  ) 1 , (4.5)
, j
m
 i 2 , 1 ,...,  1
d i m  min  d i m  1  d 0 ,m  ( i 2 , 1 ,..., m ) 1 , (4.6)
,m
, j
j
m
 j 2 , 1 ,...,  1
m
d i m  min  d i m  d m , j ;d i m  1  ,( ji  2 , 1 ,..., m ) 1 . (4.7)
, j
, j
,m
64