Page 22 - 2577

s - початковий вузол;
T - множина вузлів, які вже оброблені алгоритмом;
w - вартість каналу від вузла i до вузла j ;
ij
w  0; w  , якщо два вузли не з’єднані безпосередньо і w  при
0
ii ij ij
безпосередньому з’єднані двох вузлів;
L  n - шлях мінімальної вартості від вузла s до вузла n .
Алгоритм складається з трьох етапів. Етапи 2 і 3 повторюються до досягнення T
значення N .
1. Ініціалізація.
T   s ; множина T містить початковий вузол s .
2. Отримання наступного вузла.
Знаходимо сусідні вузли, що не входять до T , і який має шлях мінімальної вартості
від вузла s і додаємо цей вузол до множити T , тобто знайти x T таке, що  xL  min L  j .
j T
Додаємо x в T ; додаємо в T ребро графа (канал), що з’єднує з’єднане з x і яке додає
до  xL доданок мінімальної вартості.
3. Оновлення шляхів мінімальної вартості.
Знаходимо шлях мінімальної вартості від вузла x до вузла n
L  n  min L     wxLn ,   , n  T .
xn
Алгоритм закінчується коли всі вузли мережі додані до T .

Приклад 2.1. Для комп’ютерної мережі (рис. 2.4) знайти найкоротші шляхи,
використовуючи алгоритм Дейкстри.
Результати застосування алгоритму Дейкстри до графа показані у табл. 2.2
Таблиця 2.2 – Вибір маршруту мінімальної вартості за допомогою алгоритму
1
Дейкстра для рис. 2.4 (s  )

Ітерація T L  2 Шлях L  3 Шлях
1 1 2 1 – 2 5 1 – 3

2  4,1 2 1 – 2 4 1 – 4 – 3
3  2,1  4 , 2 1 – 2 4 1 – 4 – 3
4  2,1  5 , 4 , 2 1 – 2 3 1 – 4 – 5 – 3
5  2,1  5 , 4 , 3 , 2 1 – 2 3 1 – 4 – 5 – 3
6  2,1  6 , 5 , 4 , 3 , 2 1 – 2 3 1 – 4 – 5 – 3

продовження табл. 2.2
L  4 Шлях L  5 Шлях L  6 Шлях
1 1 – 4  -  -
1 1 – 4 2 1 – 4 – 5  -
1 1 – 4 2 1 – 4 – 5  -
1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 – 6
1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 – 6
1 1 – 4 2 1 – 4 – 5 4 1 – 4 – 5 – 6

На кожному етапі визначається шлях до кожного вузла і загальна вартість цього
шляху. Після завершальної ітерації визначені шляхи мінімальної вартості. Вказану процедуру
можна застосувати і для вузлів 2, 3, …, 5. Код програми представлено в додатку Б.

19