Page 26 - 4387

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

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

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

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

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

d (d ) = min{d (d );d (a ) + c (a ,d )} = min{ 4 ; 6 + } 2 = 6;

d (w ) = min{d (w );d (a ) + ( wac , )} = min{ ∞ 4; + ∞} = ∞.

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

позначаємо вершину d. Можна вважати, що величину d(b)

визначають як дуга (с, d), так і дуга (a, d). Тому можна позначити

довільну із цих дуг. Позначимо, наприклад, дугу (с, d).

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

складається з дуг (v, c), (v, а) та (с, d) (рис. 3.2 в).

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

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

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

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

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

d (w ) = min{d (w );d (d ) + c (d ,w )} = min{∞ 6 ; + } 2 = 8.

Оскільки величина d(b)=7 менша за величину d(w), то

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

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

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

(рис. 3.2 г).

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

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

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

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

25