Page 52 - 4336

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.7, в).

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

до кроку 2.

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

вершини (крім вершини b) за формулою (4.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.7, г).
Крок 3. Оскільки позначені не всі вершини, то переходимо

до кроку 2.

52