Page 31 - 4387

а б в

г д

Рисунок 4.2.

Крок 3. Оскільки позначені не всі вершини, то переходимо

до кроку 2.
Крок 2. (y=b). Розраховуємо величину d(x) для кожної з

вершини (крім вершини b) за формулою (3.1):

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

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

d (d ) = min{d (d );d (b ) + c (b ,d )} = min{∞ 3 ; + } 1 = 4;

d (e ) = min{d (e );d (b ) + c (b ,e )} = min{∞ 3 ; + } 1 = 4.

Для раніше позначеної вершини a значення d(a) не

змінилось, тому позначка з неї не знімається. Для всіх інших

вершин c, d та e значення d(x) рівні між собою, тому позначаємо

довільну з даних вершин, наприклад вершину c і відповідну дугу

(a, c). Присвоюємо у=c. Поточне дерево найкоротших шляхів

складайся з дуг (a, b) і (a, c) (рис. 4.2 б).

Крок 3. Оскільки позначені не всі вершини, то переходимо

до кроку 2.

Крок 2. (y=c). Розраховуємо величину d(x) для кожної з

вершини (крім вершини c) за формулою (3.1):

30