Page 12 - 4387

від усіх вершин графа до i-ї вершини. Приймається d=0. В i-й

-
елемент вектора Т (v ) заноситься значення d. j=i.
i i
Крок 2. Переглядається j-й стовпчик матриці суміжності A і

визначаються елементи a (i=1, 2, …, n) рівні 1.
i,j
Крок 3. Якщо жодний з елементів a ≠1, то алгоритм
i,j
-
завершується. Усім незаповненим елементам вектора Т (v )
i
присвоюється значення ∞ – це означає що від даних вершин

графа немає шляхів до вершини v . В іншому випадку
i
здійснюється перехід до кроку 4.

Крок 4. Якщо є один або більше елементів a =1, то d=d+1,
i,j
j=i (крім тих значень i, яким відповідають уже заповнені

-
елементи вектора Т (v )) та відповідним i-м елементам вектора
i
-
Т (v ) (крім уже заповнених елементів) присвоюється значення d.
i i
Це означає що від даних вершин існують шляхи довжиною d до
-
вершини v . Якщо усі елементи вектора Т (v ) заповнені, то
i
i
алгоритм завершує свою роботу. В іншому випадку здійснюється

перехід до кроку 5.

Крок 5. Переглядаються відповідні j-ті стовпчики матриці

суміжності A і визначаються елементи a (i=1, 2, …, n) рівні 1.
i,j
Здійснюється перехід до кроку 3.

Приклад 1.4. Знайти зворотне транзитивне замикання по

матриці суміжності, наведеної на рис. 1.2 а, для вершини v
3
графа, наведеного на рис. 1.2 б.

Розв'язок.

-
Крок 1. Формується вектор Т (v ) з шести елементів (рис.
3
-
1.4). d=0, Т (v ) →d, j=3.
3 3
Крок 2. Переглядаємо j-й стовпчик матриці А (3-й
стовпчик): a =1, a =1.
1,3
4,3

11