вже оброблених алгоритмом; L (n) - мінімальна вартість шляху від вершини s до вершини п, відомого на даний момент алгоритмом (по завершенні роботи алгоритму це мінімальна вартість шляху від вершини s до вершини п). Алгоритм складається з трьох кроків. Кроки 2 і 3 повторюються до тих пір, поки безліч T не збіжиться з безліччю N. Це означає, що кроки 2 і 3 повторюються, поки для всіх вершин мережі не будуть знайдені остаточні шляху. p align="justify">. Ініціалізація.
Т = Дерево = {s}, тобто безліч досліджених вершин складається поки що тільки з вершини-джерела. Вартістю початкових шляхів до сусідніх вершин являють собою просто вартості ліній зв'язку. p align="justify">. Отримати наступну вершину.
Знайти наступну вершину, що не належить безлічі T і має шлях від вершини s з мінімальною вартістю, і включити цю вершину в безліч T і в Дерево. Крім того, до дерева додається ребро, інцідентное цій вершині і вершині безлічі T, що входить в дорогу з мінімальною вартістю. Тобто знаходимо вершину x ГЏ Т таку, що
L (x) = min L (j) ГЏ T
Додати вершину х до безлічі T і до дерева; додати до дерева ребро, інцідентное вершині х, яке складає компонент шляху L (x) з мінімальною вартістю - останній ретрансляційний ділянку шляху.
. Оновити шлях з мінімальною вартістю.
L (n) = min [L (n), L (x) + w (x, п)] для всіх п ГЏ Т.
Якщо остання величина мінімальна, то з цього моменту шлях від вершини до вершини п являє собою конкатенацію шляху від вершини s до вершини х і шляху від вершини х до вершини п. Алгоритм завершує роботу, коли всі вершини додані до безлічі Т.
Таблиця 1 - Результати роботи алгоритму Дейкстри для заданого графа
? 2 - 1-5-3 ? 2 - 1-5-4? 1-511-63 {1,5,6} 31-22 31-5-3 1-6-321 - 5-4? 1-511-64 {1,5,6,3} 3 81-2 1-5-3-221-5-321-5-4? 1-51 81-6 1-5-3 - 65 {1,5,6,3,4} 3 81-2 1-5-4-221-5-321-5-411-511-66 {1,5,6,3,4,2} 31 - 22 101-5-3 1-2-32 101-5-4 1-2-411-511-6ІТОГ31-221-5-321-5-411-511-6
В
Рисунок 3 - Застосування алгоритму Дейкстри до графа, представленому на рис. 2.1
4. Алгоритм Беллмана-Форда
мережа граф маршрутизація алгоритм
Алгоритм Беллмана-Форда може бути сформульовано таким чином: потрібно знайти найкоротші шляхи від заданої вершини за умови, що ці шляхи скл...
