Алгоритм Воршелла

Алгоритм Воршелла— це ефективний метод побудови транзитивного замкнення на відношенні R. Дія цього алгоритму полягає в перетворенні вхідної матриці M_R , яка відображає відношення R, в вихідну транспоновану матрицю M_R* на відношенні R^*. В свою чергу R^* є транзитивним замкненням від відношення R.

Принцип дії алгоритму

Задано відношення R на n-елементарній множині А={a₁,a₂,a₃,…,a_n}. Алгоритм Воршелла будує послідовність булевих матриць W⁰,W¹, W², … , Wⁿ, де W⁰=M_R — матриця відношення R. Елементи матриці W^(k) позначимо як w^(k)_ij. Якщо існує шлях із вершини a_i до вершини a_j такий, що всі його внутрішні вершини містяться в множині {a₁,a₂,a₃,…,a_n}, утвореній першими k вершинами, то w^(k)_ij=1, а ні, то w^(k)_ij =0. Перша й остання вершини такого шляху можуть і не належати множині вершин {a₁,a₂,a₃,…,a_k}. Зазначимо, що Wⁿ=M_R*. Алгоритм Воршелла ефективно обчислює матрицю W^(k) за матрицею W^(k-1). Шлях із вершини a_i у вершину a_j із внутрішніми вершинами в множині {a₁,a₂,a₃,…,a_k} існує лише в двох випадках:

1. Якщо існує шлях із вершини a_i у вершину a_j із внутрішніми вершинами лише в множині {a₁,a₂,a₃,…,a_k-1}.

2. Якщо існує шлях із вершини a_i у вершину a_k та шлях із вершини a_k у вершину a_j, і кожний із цих шляхів має внутрішні вершини лише в множині {a₁,a₂,a₃,…,a_k}

У випадку 1 шлях існує тоді і лише тоді, коли w^(k-1)_ij=1, у випадку 2 — коли обидва елементи w^(k-1)_ik та w^(k-1)_kj дорівнюють 1. Отже, w^(k)_ij = w^(k-1)_ij˅(w^(k-1)_ik ˄w^(k-1)_kj), k=1,2,…,n.

Формула для практичної реалізації

Окрім того очевидно, що в разі i=k дії в першому рядку формули можна не виконувати. Отже,

Остання формула дає таке правило переходу від матриці W^(k-1) до матриці W^(k): для значень i≠k в разі w^(k-1)_ik=1 замінити i-й рядок матриці W^(k-1) на диз'юнкцію i-го й j-го рядків цієї матриці.

Формальний алгоритм Воршелла

(i та j змінюються від 1 до n)

1. Виконати W=M_R, k=0. Ітерація.
2. Виконати k=k+1;
3. Для всіх i≠k таких, що w_ik=1 і для всіх j виконати операцію w_ij=w_ij˅w_kj. Перевірка закінчення.
4. Якщо k=n, то зупинитись. Отримано розв'язок W = M_R*. В іншому випадку перейти до кроку 2.

Приклад

Відношення задано матрицею :

За алгоритмом Уоршалла побудуємо транзитивне замкнення цього відношення. Для k=1 перший рядок залишаємо без змін (i=k), другий і третій рядки замінюємо на диз'юнкцію кожного з них із першим :

Для k=2 отримаємо, що W(2)=W(1), бо всі елементи другого стовпця матриці W(1) нульові. Далі, для k=3 одержимо :

І, нарешті, коли k=4 матимемо остаточний результат — матрицю транзитивного замкнення :

Див. також

Алгоритм Флойда — Уоршелла

Джерела

Rosen, Kenneth H., Discrete Mathematics and its Applications, Third Edition, McGraw-Hill, Inc,1994.