Page 25 - 4387

d (w ) = min{d (w );d (v ) + ( wvc , )} = min{ ∞ 0; + ∞} = ∞.

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

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

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

найкоротших шляхів складайся з дуги (v, c) (рис. 3.2 а).

а б в

г д

Рисунок 3.2. Наростаюче орієнтоване дерево найкоротших

шляхів

Крок 3. Оскільки вершина w залишається непозначеною,

переходимо до кроку 2.

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

непозначених вершини за формулою (3.1):

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

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

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

d (w ) = min{d (w );d (c ) + ( wcc , )} = min{ ∞ 3; + ∞} = ∞.

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

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

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

найкоротших шляхів складається з дуг (v, c) та (v, а) (рис. 3.2 б).

24