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

Задача

Пусть дано отношение [math]R[/math] на множестве [math]X[/math]. Необходимо построить его транзитивное замыкание [math]\mathrm{TrCl}(R)[/math].

Алгоритм

Пусть вершины графа [math]G=(V,\; E),\; |V| = n[/math] пронумерованы от 1 до [math]n[/math]. Каждая вершина соответствует элементу множества. А наличие ребра между вершинами означает, что соответствующие элементы множества состоят в отношении. Пусть так же введено булево обозначение [math]d_{i j}^{k}[/math] для наличия пути (равно true, если есть путь, и false — в противном случае) от [math]i[/math] до [math]j[/math], который кроме самих вершин [math]i,\; j[/math] проходит только через вершины [math]1 \ldots k[/math](с номерами [math] \le k [/math]).

Тогда существующий путь между [math]i,\;j[/math], проходящий через [math]k[/math] (сначала он идет от [math]i[/math] до [math]k[/math], а потом от [math]k[/math] до [math]j[/math]), очевидно, выражается, как [math]d_{i j}^{k}=d_{i k}^{k-1} \cap d_{k j}^{k-1}[/math]

Алгоритм Флойда — Уоршелла последовательно вычисляет все значения [math]d_{i j}^{k}[/math], [math]\forall i,\; j[/math] для [math]k[/math] от 1 до [math]n[/math]. Полученные значения [math]d_{i j}^{n}[/math] являются транзитивным замыканием графа.

Псевдокод

На каждом шаге алгоритм генерирует двумерную матрицу [math]W[/math], [math]w_{ij}=d_{i j}^n[/math]. Матрица [math]W[/math] содержит транзитивное замыкание графа. Перед работой алгоритма матрица [math]W[/math] заполняется true или false в зависимости от наличия ребра в графе.

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i][j] = W[i][j] or (W[i][k] and W[k][j])

Сложность алгоритма

Три вложенных цикла содержат операцию, исполняемую за константное время. [math]\sum_{n,\;n,\;n}O(1) = O(n^3),[/math] то есть алгоритм имеет кубическую сложность, при этом простым расширением можно получить также информацию о кратчайших путях — помимо расстояния между двумя узлами записывать матрицу идентификатор первого узла в пути.

Ссылки

• Реализация алгоритма Флойда на С++
• Реализация алгоритма Флойда на Delphi
• Визуализатор
• Википедия — свободная энциклопедия