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

Задача

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

Алгоритм

Сформулируем нашу задачу в терминах графов: рассмотрим граф [math]G=(V,\; E),\; |V| = n[/math], соответствующий отношению [math]R[/math]. Тогда необходимо найти все пары вершин [math](x, y) [/math], соединенных некоторым путем. Иными словами, требуется построить новое отношение [math]T[/math], которое будет состоять из всех пар [math](x, y) [/math] таких, что найдется последовательность [math]x = x_0, x_1, \dots, x_k = y [/math], где [math] (x_{i-1}, x_i) \in R, i = 1, 2, \dots, k [/math].

Псевдокод

Изначально матрица [math]W[/math] заполняется соответственно отношению [math]R[/math], то есть [math]W[i][j] = [(i, j) \in R] [/math]. Затем внешним циклом перебираются все элементы [math]k[/math] множества [math]X[/math] и для каждого из них, если он может использоваться, как промежуточный для соединения двух элементов [math]i[/math] и [math]j[/math], отношение [math]T[/math] расширяется добавлением в него пары [math](i, j)[/math].

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])

Доказательство

<wikitex>Назовем промежуточной вершину некоторого пути $p = \left \langle v_0, v_1, \dots, v_k \right \rangle$, принадлежащую множеству вершин этого пути и отличающуюся от начальной и конечной вершин, то есть принадлежащую $\left \{ v_1, v_2, \dots, v_{k-1} \right \}$. Рассмотрим произвольную пару вершин $i, j \in V$ и все пути между ними, промежуточные вершины которых принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k \right \}$. Пусть $p$ - кратчайший из них. Рассмотрим случаи:

• $k$ не является промежуточной вершиной пути $p$. Тогда все его промежуточные пути принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$, что и требуется.
• $k$ является промежуточной вершиной пути $p$. Тогда этот путь можно разбить на два пути: $i \xrightarrow{p_1} k \xrightarrow{p_2} j$. Как $p_1$, так и $p_2$ являются кратчайшими путями между соответствующими вершинами $i, k$ и $k, j$ с промежуточными вершинами из множества $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$ (так как вершина $k$ - либо конечная, либо начальная, то она не может быть в множестве по нашему определению). Действительно, если они не являются таковыми, то заменим эти подпути пути $p$ на кратчайшие. Тогда сам путь $p$ не будет кратчайшим, что является противоречием.

Во время работы алгоритма будут просмотрены все возможные разбиения на соответствующие пути для каждой пары вершин и выбран лучший из них. По его окончании транзитивное замыкание будет построено корректно. </wikitex>

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

Три вложенных цикла работают за время [math]\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)[/math], то есть алгоритм имеет кубическую сложность.

Ссылки

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

Источники

• Романовский И. В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. Изд. 3-е. — СПб.: Невский диалект, 2003. — 320 с. — ISBN 5-7940-0114-3.