Page 53 - 4336

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

вершини (крім вершини d) за формулою (4.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.7, д).

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

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

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

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

вершини (крім вершини e) за формулою (4.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.7, д) і має

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

53