Page 32 - 4387

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

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

d (d ) = min{d (d );d (c ) + c (c ,d )} = min{ 4 ; 4 + } 5 = 4;

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

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

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

b значення d(b) зменшилось, тому позначка з цієї вершини, а

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

найменше значення d(x) має вершина b, тому позначаємо її

заново, а також дугу (c, b). Присвоюємо у=b. Поточне дерево

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

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

до кроку 2.

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

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

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

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

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

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

Для раніше позначених вершин значення d(x) не змінилось,

тому позначки з них не знімаємо. Для непозначених вершин d та

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

даних вершин, наприклад вершину d і відповідну дугу (b, d).

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

з дуг (a, c), (c, b) та (b, d) (рис. 4.2 г).

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

до кроку 2.

31