Редактирование: Алгоритм Флойда — Уоршалла

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Алгоритм Флойда]]
+
==Задача==
 +
Пусть дано [[Определение отношения|отношение]] <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])
 +
 
 +
=== Сложность алгоритма ===
 +
Три вложенных цикла работают за время <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.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)