Page 63 - 4336

Отже, розглянемо алгоритм Данцига. Знову занумеруємо

вершини вихідного графа цілими числами від 1 до N і позначимо

через довжину найкоротшого шляху з вершини i у вершину j,
,
у якому допускається використання в якості проміжних m

перших вершин графа. Нехай тепер, на відміну від алгоритму

Флойда-Уоршола, матриця D , що складається з величин ,
,
при кожному m=1, 2, ..., N має розмірність не N×N, а m×m. Так

само, як і раніше, необхідно визначити матрицю D , елементи

якої, визначають довжини найкоротших шляхів між i-ми та
,
j-ми вершинами. Як і в алгоритмі Флойда-Уоршола, в алгоритмі

Данцига матриця D визначається з матриці D , матриця D з

матриці D і т.д. Нарешті, матриця D визначається з матриці
D .

Ідея алгоритму Данцига полягає в наступному. Кожна нова

матриця D , що обчислюється, містить на один рядок і на один

стовпець більше, чим її попередниця, матриця D . Елементи

матриці D , що не входять в останній рядок і стовпець (число

2
таких елементів рівне (m-1) ), визначаються аналогічно, як і в
алгоритмі Флойда-Уоршола. Що ж стосується інших елементів

, де i=m або j=m, то вони визначаються виходячи з наведених
,
нижче міркувань. Найкоротший шлях з вершини i у вершину j

(або навпаки), у якому допускається використання в якості

проміжних тільки перших m вершин графа, не може мати серед

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

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

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

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

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

63