Page 30 - 4387

2. Якщо для деякої позначеної вершини х відбувається

зменшення величини d(x), то із цієї вершини та інцидентної їй

позначеної дуги позначення знімається.

3. Процедура алгоритму закінчується тільки тоді, коли усі

вершини позначені та коли після виконання кроку 2 жодне із

чисел d(x) не змінюється.

Приклад 4.1. Використовуючи алгоритм Белмана-Форда,
знайти у графі, зображеному на рис. 4.1, найкоротший шлях між

вершинами a та е.

Рисунок 4.1.

Розв'язок.

Крок 1. Позначаємо вершину a. Вважаємо, що d(a)=0,
d(x)=∞, для всіх вершин х, які не збігаються з a. Присвоюємо у=a.

Крок 2. (y=a). Розраховуємо величину d(x) для кожної з
вершини (крім вершини а) за формулою (3.1):

d (b ) = min{d (b );d (a ) + c (a ,b )} = min{∞ 0 ; + } 3 = 3;

d (c ) = min{d (c );d (a ) + c (a ,c )} = min{∞ 0 ; + } 4 = 4;

d (d ) = min{d (d );d (a ) + ( dac , )} = min{ ∞ 0 ; + ∞} = ∞;

d (e ) = min{d (e );d (a ) + (ac ,e )} = min{ ∞ 0; + ∞} = ∞ .

Оскільки величина d(b)=3 є мінімальною з величин d(x), то

позначаємо вершину b. Так само позначаємо і дугу (a, b), яка і

визначає величину d(b). Присвоюємо у=b. Поточне дерево

найкоротших шляхів складайся з дуги (a, b) (рис. 4.2 а).

29