|
|
| (не показано 26 промежуточных версий 8 участников) |
| Строка 1: |
Строка 1: |
| − | ==Задача==
| + | #перенаправление [[Алгоритм Флойда]] |
| − | Пусть дано отношение <tex>R</tex> на множестве <tex>X</tex>. Необходимо построить его [[Транзитивное замыкание|транзитивное замыкание]] <tex>\mathrm{TrCl}(R)</tex>.
| |
| − | == Алгоритм ==
| |
| − | Пусть вершины графа <tex>G=(V,\; E),\; |V| = n</tex> пронумерованы от 1 до <tex>n</tex>. Каждая вершина соответствует элементу множества. А наличие ребра между вершинами означает, что соответствующие элементы множества состоят в отношении. Пусть так же введено булево обозначение <tex>d_{i j}^{k}</tex> для наличия пути (равно true, если есть путь, и false {{---}} в противном случае) от <tex>i</tex> до <tex>j</tex>, который кроме самих вершин <tex>i,\; j</tex> проходит только через вершины <tex>1 \ldots k</tex>(с номерами <tex> \le k </tex>).
| |
| − | | |
| − | Тогда существующий путь между <tex>i,\;j</tex>, проходящий через <tex>k</tex> (сначала он идет от <tex>i</tex> до <tex>k</tex>, а потом от <tex>k</tex> до <tex>j</tex>), очевидно, выражается, как <tex>d_{i j}^{k}=d_{i k}^{k-1} \cap d_{k j}^{k-1}</tex>
| |
| − | | |
| − | Алгоритм Флойда — Уоршелла последовательно вычисляет все значения <tex>d_{i j}^{k}</tex>, <tex>\forall i,\; j</tex> для <tex>k</tex> от 1 до <tex>n</tex>. Полученные значения <tex>d_{i j}^{n}</tex> являются транзитивным замыканием графа. | |
| − | | |
| − | === Псевдокод ===
| |
| − | | |
| − | На каждом шаге алгоритм генерирует двумерную матрицу <tex>W</tex>, <tex>w_{ij}=d_{i j}^n</tex>. Матрица <tex>W</tex> содержит транзитивное замыкание графа. Перед работой алгоритма матрица <tex>W</tex> заполняется 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])
| |
| − | | |
| − | === Сложность алгоритма ===
| |
| − | Три вложенных цикла содержат операцию, исполняемую за константное время.
| |
| − | <tex>\sum_{n,\;n,\;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/Заглавная_страница Википедия — свободная энциклопедия]
| |
