Page 62 - 4336

0 1 2 1  ) 2 , 1 ( ) 3 , 1 ( ) 4 , 1 (

D 2  2 0 4 3 , D  2  ) 1 , 2 (  ) 3 , 1 , 2 ( ) 4 , 1 , 2 ( .
6 5 0 2 ) 1 , 3 ( ) 2 , 3 (  ) 4 , 3 (

1 2 3 0 ) 1 , 4 ( ) 2 , 1 , 4 ( ) 3 , 1 , 4 ( 

Аналогічним чином визначаються елементи матриць D та

D і відповідні їм матриці найкоротших шляхів. Одержані

результати наведені нижче.

0 1 2 1  ) 2 , 1 ( ) 3 , 1 ( ) 4 , 1 (

D 3  2 0 4 3 , D  3  ) 1 , 2 (  ) 3 , 1 , 2 ( ) 4 , 1 , 2 ( .
6 5 0 2 ) 1 , 3 ( ) 2 , 3 (  ) 4 , 3 (

1 2 3 0 ) 1 , 4 ( ) 2 , 1 , 4 ( ) 3 , 1 , 4 ( 

0 1 2 1  ) 2 , 1 ( ) 3 , 1 ( ) 4 , 1 (

D 4  2 0 4 3 ,D  4  ) 1 , 2 (  ) 3 , 1 , 2 ( ) 4 , 1 , 2 (
3 4 0 2 ) 1 , 4 , 3 ( ) 2 , 1 , 4 , 3 (  ) 4 , 3 (

1 2 3 0 ) 1 , 4 ( ) 2 , 1 , 4 ( ) 3 , 1 , 4 ( 

Слід відмітити, що при довільній нумерації вершин вхідного
графа, в процесі виконання алгоритму найкоротші шляхи будуть

відшукуватися на більш ранніх стадіях для тих вершин, які,
маючи “близькі” номери, є “близькими” і по довжинах

відповідних найкоротших шляхів.

4.3.2 Алгоритм Данцига

Ще один алгоритм пошуку на графі найкоротших шляхів

між усіма парами вершин запропонований американським

математиком Джорджем Данцигом. Алгоритм Данцига досить

близький до алгоритму Флойда-Уоршола та відрізняється від

останнього лише іншим порядком виконання тих самих операцій.

62