Изменения

Перейти к: навигация, поиск

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

5649 байт убрано, 19:39, 27 декабря 2015
Перенаправление на Алгоритм Флойда
==Задача==Пусть дано #перенаправление [[Определение отношения|отношение]] <tex>R</tex> на множестве <tex>X</tex>. Необходимо построить его [[Транзитивное замыкание|транзитивное замыкание]] <tex>T = \mathrm{TrCl}(R)</tex>. == Алгоритм ==Сформулируем нашу задачу в терминах графов: рассмотрим граф <tex>G=(V,\; E),\; |V| = n</tex>, соответствующий отношению <tex>R</tex>. Тогда необходимо найти все пары вершин <tex>(x, y) </tex>, соединенных некоторым путем.Иными словами, требуется построить новое отношение <tex>T</tex>, которое будет состоять из всех пар <tex>(x, y) </tex> таких, что найдется последовательность <tex>x = x_0, x_1, \dots, x_k = y </tex>, где <tex> (x_{i-1}, x_i) \in R, i = 1, 2, \dots, k </tex>. === Псевдокод ===Изначально матрица <tex>W</tex> заполняется соответственно отношению <tex>R</tex>, то есть <tex>W[i][j] = [(i, j) \in R] </tex>. Затем внешним циклом перебираются все элементы <tex>k</tex> множества <tex>X</tex> и для каждого из них, если он может использоваться, как промежуточный для соединения двух элементов <tex>i</tex> и <tex>j</tex>, отношение <tex>T</tex> расширяется добавлением в него пары <tex>(i, j)</tex>.  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$ существуют и содержат в качестве промежуточных вершины из множества $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$ (так как вершина $k$ - либо конечная, либо начальная, то она не может быть в множестве по нашему определению). Действительно, если они не существуют, то пути $p$ тоже не может существовать, так как добраться, например, от вершины $i$ до $k$ по вершинам из множества \left \{ 1, 2, \dots, k \right \} невозможно. Но этого быть не может по тому, как мы определили путь $p$.Во время работы алгоритма будут просмотрены все возможные разбиения на соответствующие пути для каждой пары вершин и, при возможности, будет построен путь. По его окончании транзитивное замыкание будет построено корректно.</wikitex> === Сложность алгоритма ===Три вложенных цикла работают за время <tex>\sum\limits_{n}\sum\limits_{n}\sum\limits_{n}O(1) = O(n^3)</tex>, то есть алгоритм имеет кубическую сложность. == Ссылки ==* [http://e-maxx.ru/algo/floyd_warshall_algorithm Реализация алгоритма Флойда на С++]* [http://plagiata.net.ru/?p=57 Реализация алгоритма Флойда на Delphi]* [http://rain.ifmo.ru/cat/data/vis/graph-paths/floyd-warshall-2004/code.jar Визуализатор]* [http://ru.wikipedia.org/wiki/Заглавная_страница Википедия — свободная энциклопедия== Источники ==* Романовский И. В. '''Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике'''. Изд. 3-е. — СПб.: Невский диалект, 2003. — 320 с. — ISBN 5-7940-0114-3.
188
правок

Навигация