Алгоритмы\Алгоритм Уоршалла

Транзитивное замыкание графа. Алгоритм Уоршалла

Транзитивным называется граф, в котором из существования дуг (x_i,x_j) и (x_j,x_k) следует сущестование дуги (x_i,x_k). Транзитивным замыканием графа G называется граф G'=(V,E∪E'), где E' - минимальное множество дуг , которое следует добавить к графу G, чтобы он стал транзитивным. Для построения транзитивного замыкания графа можно воспользоваться алгоритмом Уоршалла. Его сложность - O(n³).
Пусть C - матрица смежности данного графа. C[i,j]=1, если существует дуга из вершины i в вершину j, и C[i,j]=0 в противном случае.
Вычислим матрицу A (транзитивное замыкание матрицы смежности), такую что A[i,j]=1 тогда и только тогда, когда существует путь из вершины i в вершину j, и A[i,j]=0, если такого пути нет.

A⁰[i,j]=C[i,j]
A^k+1[i,j]=A^k[i,j] or (A^k[i,k+1] and A^k[k+1,j])

Заметим, что вычисления очень схожи с вычислениями в алгоритме Флойда для нахождения кратчайших путей между всеми парами вершин.

Скачать исходник (Pascal)

| Главная | Общие сведения | Глоссарий | Алгоритмы | Программы | Литература | Ссылки |

© JlC, 2005