Page 67 - 4336

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

d 3 2 , 3  min  d 0 1 , 3  d 2 2 , 1 ;d 0 2 , 3  d 2 2 , 2  min  6 5 ; 1  0  5 (3, 2)

d 3  min  d 3  d 3 ;d 2  min  2 1 ; 5  1 (1, 2)
2 , 1 3 , 1 2 , 3 2 , 1

d 3  min  d 3 d 3 ;d 2  min  4 2 ; 6  2 (2, 1)
1 , 2 3 , 2 1 , 3 1 , 2

Матриця D та матриця найкоротших шляхів D для

елементів матриці D є наступними:
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 ( 

Слід відзначити, що обчислена вище матриця D збігається з

лівою верхньою підматрицею розмірністю 3×3 матриці D , що
одержана в прикладі 4.4 за допомогою алгоритму Флойда-

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

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

4.4 Алгоритм подвійного пошуку k перших найкоротших

шляхів

При розв'язку деяких практичних завдань, пов'язаних з

транспортними мережами, необхідно знайти не один, а кілька

найкоротших шляхів, розташованих у порядку зростання їх

довжин. Наприклад, знання декількох найкоротших шляхів у

мережі вулиць дозволить планувальникам транспортних мереж

більш точно моделювати потоки руху автомобілів по вулицях

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

недоступні, можуть бути використані відомості про найкращі з

можливих альтернативних варіантів.

67