Page 48 - 4387

Відповідні
3
Елементи матриці D
шляхи

=
d 3 2 , 1 = min { d 3 3 , 1 + d 3 2 , 3 ;d 2 2 , 1 } min += {2 1 ; 5 } 1 (1, 2)

d 3 1 , 2 = min { d 3 3 , 2 + d 3 1 , 3 ;d 2 1 , 2 } min += {4 2 ; 6 } 2 (2, 1)
=

Матриця та матриця найкоротших шляхів для
′
3
3
елементів матриці є наступними:
3
0 1 2 − ) 2 , 1 ( ) 3 , 1 (
D 3 = 2 0 4 , D ′ 3 = 2( ) 1 , − ) 3 , 1 , 2 ( .

6 5 0 ) 1 , 3 ( ) 2 , 3 ( −

Слід відзначити, що обчислена вище матриця збігається з
3
лівою верхньою підматрицею розмірністю 3×3 матриці , що
3
одержана в прикладі 5.1 за допомогою алгоритму Флойда-

Уоршола. Аналогічним чином обчислюється матриця , яка
4

повністю співпадає з матрицею з прикладу 5.1.
4

6.3 Порядок виконання роботи

Варіант № 1

1. Використовуючи алгоритм Данцига, знайти у графі,

наведеному на рис. 6.1 а, найкоротші шлях між усіма вершинами.

Варіант № 2

1. Використовуючи алгоритм Данцига, знайти у графі,

наведеному на рис. 6.1 б, найкоротші шлях між усіма вершинами.

47