Page 23 - 2577

Алгоритм Беллмана-Форда формулюється так:
знайти найкоротші шляхи від даного початкового вузла за умови, що шляхи
вміщують не більше одного каналу; потім знайти найкоротші шляхи, що вміщують не більше
двох каналів і т. д.
Отже, нехай
s - початковий вузол;
w - вартість каналу від вузла i до вузла j ;
ij
w  0 ; w   , якщо два вузли не з’єднані безпосередньо і w  0 при
ii ij ij
безпосередньому з’єднані двох вузлів;
h - максимальне число каналів для шляху на поточному етапі алгоритму;
L  n - шлях мінімальної вартості від вузла s до вузла n , який вміщує не більше
h каналів.
Алгоритм складається із двох кроків – ініціалізації та модифікації.
1. Ініціалізація.
  nL 0 для всіх n  ;
s
  0sL h для всіх h .
2. Модифікація.
Для кожного наступного h 0:
для кожного n  обчислимо
s
L  n  min L   wj  .
h1 h jn
j
З’єднуємо n з попереднім вузлом j , який має мінімальну вартість і вилучаємо
з'єднання n з іншим попереднім вузлом, який побудованій на попередній ітерації. Шлях від
s закінчується каналом від j до n .
Для ітерації другого етапу при h  для кожного вузла призначення n алгоритм
k
порівнює можливі шляхи від s до n довжини k  1з шляхом, який визначений на
попередній ітерації. Якщо попередній шлях має меншу вартість, він зберігається на новій
ітерації. У протилежному випадку визначається новий шлях довжиною k 1 від s до n . Цей
шлях складається із шляху довжини k і прямого каналу від вузла j до вузла n . Ітераційний
процес закінчується, коли h 1  n.
Приклад 2.1. Для мережі, топологія якої показана на рис. 2.4, знайти шлях
мінімальної довжини від вузла 1 до вузла 6, використавши алгоритм Беллмана-Форда.
У табл. 2.3 показані результати застосування алгоритму Беллмана-Форда до топології,
яка показана на рис. 2.4 для s  . На кожному етапі шукаються шляхи мінімальної вартості
1
з максимальним числом каналів, яке дорівнює h . Після завершальної ітерації визначені
шляхи мінімальної вартості до кожного із каналів і вартості цих шляхів. Таку процедуру
можна застосувати, коли початковими вузлами будуть вузол 2, вузол 3 і т. д.
Лавинна маршрутизація Лавинна маршрутизація не вимагає ніякої апріорної
інформації про мережу. Її суть полягає в тому, що вузол відправлення посилає пакети до всіх
сусідніх вузлів. На кожному вузлі прийняті пакети ретранслюються на всі вихідні канали,
крім каналу, з якого він поступив. Наприклад, із вузла 1 (рис. 2.4) необхідно послати пакет
до вузла 5. Тоді вузол 1 посилає пакети до вузлів 2, 3 і 4; вузол 2 посилає копію пакета на 3,
4; вузол 4 посилає копію на 2, 3, і 5 і т. д. Кожна копія повинна мати унікальний
ідентифікатор (наприклад, номер вихідного вузла і порядковий номер або номер
віртуального каналу і порядковий номер), щоб вузол 6 міг анулювати всі копії крім
останньої.

20