Page 45 - 4387

проміжних вершину m, оскільки будь-який контур у вихідному

графі не має від'ємної довжини. Отже, такий найкоротший шлях з

вершини i у вершину m повинен мати своєю першою частиною

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данцига.

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

числами від 1 до N. Сформувати матрицю , (розмірністю N×N),
0
кожний елемент якої визначає довжину найкоротшої дуги, що
0
,
веде з вершини i у вершину j. При відсутності такої дуги

0 = ∞.
присвоїти
,
Крок 2. Через позначається матриця розмірністю m×m з

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

,
−1 для m, що приймає
матриці за елементами матриці
значення 1, 2, ..., N:

44