Page 33 - 4387

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

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

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

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

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

d (e ) = min{d (e );d (d ) + c (d ,e )} = min{− ; 3 − 3+ (− 2 )} = − 5.

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

тому позначки з них не знімаємо. Залишилась тільки одна

непозначена вершина e, яку позначаємо на даному кроці, а також

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

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

(рис. 4.2 д).

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

перехід до кроку 2 для того, щоб спробувати зменшити значення

d(x) для позначених вершин.

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

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

d (a ) = min{d (a );d (e ) + c (e ,a )} = min{ ; 0 − 5 ∞+ } = 0;

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

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

d (d ) = min{d (d );d (e ) + c (e ,d )} = min{− ; 3 − 5 ∞+ } = − 3.

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

Крок 3. Оскільки позначені усі вершини графа і на

попередньому кроці алгоритму для жодної з позначених вершин

не вдалось зменшити значення d(x), то процедура алгоритму

завершується. Найкоротший шлях з вершини a у вершину e

складається з дуг (a, c), (c, b), (b, d), (d, e) (рис. 4.2 д) і має

довжину d(e)=-5.

32