Алгоритм Флойда — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Начинаем)
 
(Почти готово. Осталось добавить пример)
Строка 4: Строка 4:
  
 
== Алгоритм ==
 
== Алгоритм ==
 +
[[Файл:Floyd.png|right|thumb|Текущий (синий) путь и потенциально более короткий (красный)]]
 
Пусть дан граф <tex>G(V,E)</tex>; <tex>\omega_{uv} =
 
Пусть дан граф <tex>G(V,E)</tex>; <tex>\omega_{uv} =
 
\begin{cases}
 
\begin{cases}
Строка 12: Строка 13:
 
Обозначим длину кратчайшего пути между вершинами <tex>u</tex> и <tex>v</tex>, содержащего, помимо самих вершин <tex>u</tex> и <tex>v</tex>, только вершины с номерами <tex>1 .. i</tex> как <tex>d_{uv}^i</tex>.
 
Обозначим длину кратчайшего пути между вершинами <tex>u</tex> и <tex>v</tex>, содержащего, помимо самих вершин <tex>u</tex> и <tex>v</tex>, только вершины с номерами <tex>1 .. i</tex> как <tex>d_{uv}^i</tex>.
 
Понятно, что <tex>d_{uv}^0 = \omega_{uv}</tex>.
 
Понятно, что <tex>d_{uv}^0 = \omega_{uv}</tex>.
 +
 +
На каждом шаге алгоритма, мы будем брать очередную вершину (пусть, её номер <tex>i</tex>) и для всех пар вершин <tex>u</tex> и <tex>v</tex> вычислять <tex>d_{uv}^i = min(d_{uv}^{i-1}, d_{ui}^{i-1} + d_{iv}^{i-1})</tex>. Т.е., если кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины с номерами <tex>1 .. i</tex>, проходит через вершину <tex>i</tex>, то пройдём сначала из <tex>u</tex> в <tex>i</tex>, затем из <tex>i</tex> в <tex>v</tex>, иначе ничего менять не будем.
 +
 +
=== Код (в первом приближении) ===
 +
  # Инициализация
 +
  d[0] = w
 +
  # Основная часть
 +
  for i in {1..n}:
 +
    for u in {1..n}:
 +
      for v in {1..n}:
 +
        d[i][u][v] = min(d[i-1][u][v], d[i-1][u][i] + d[i-1][i][v])
 +
 +
=== Код (окончательный) ===
 +
Заметим, что для заполнения <tex>i</tex>-того слоя массива используются только значения из <tex>(i-1)</tex>-го слоя. Таким образом, от первого индекса вообще можно отказаться.
 +
 +
  # Инициализация
 +
  d = w
 +
  # Основная часть
 +
  for i in {1..n}:
 +
    for u in {1..n}:
 +
      for v in {1..n}:
 +
        d[u][v] = min(d[u][v], d[u][i] + d[i][v])
 +
 +
Алгоритм всегда завершит работу за <tex>O(V^3)</tex> — как не сложно видеть, три вложенных цикла выполняются по <tex>n</tex> раз каждый.
 +
 +
=== Пример работы ===
 +
Здесь пример, да
 +
 +
== Вывод кратчайшего пути ==
 +
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>t_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.
 +
 +
=== Модифицированный алгоритм ===
 +
 
 +
  # Инициализация
 +
  d = w
 +
  t[u][v] = v если есть ребро uv
 +
  # Основная часть
 +
  for i in {1..n}:
 +
    for u in {1..n}:
 +
      for v in {1..n}:
 +
        if (d[u][i] + d[i][v]) < d[u][v]:
 +
          d[u][v] = d[u][i] + d[i][v]
 +
          t[u][v] = t[u][i]
 +
 +
  # Вывод кратчайшего пути
 +
  def get_shortest_path(u, v):
 +
    if d[u][v] == inf:
 +
        raise NoPath # Из u в v пути нет
 +
    c = u
 +
    while c != v:
 +
      yield c
 +
      c = t[c][v]
 +
    yield v
 +
 +
[[Файл:Floyd_path.png]]

Версия 00:25, 22 декабря 2010

Эта статья находится в разработке!

Алгоритм Флойда (алгоритм Флойда–Уоршелла) — динамический алгоритм нахождения длин кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Разработан в 1962 году.

Алгоритм

Текущий (синий) путь и потенциально более короткий (красный)

Пусть дан граф [math]G(V,E)[/math]; [math]\omega_{uv} = \begin{cases} \text{weight of }uv ,& \text{if } uv \in E \\ +\infty ,& \text{if } uv \notin E \end{cases}[/math]; вершины пронумерованы от [math]1[/math] до [math]n[/math].

Обозначим длину кратчайшего пути между вершинами [math]u[/math] и [math]v[/math], содержащего, помимо самих вершин [math]u[/math] и [math]v[/math], только вершины с номерами [math]1 .. i[/math] как [math]d_{uv}^i[/math]. Понятно, что [math]d_{uv}^0 = \omega_{uv}[/math].

На каждом шаге алгоритма, мы будем брать очередную вершину (пусть, её номер [math]i[/math]) и для всех пар вершин [math]u[/math] и [math]v[/math] вычислять [math]d_{uv}^i = min(d_{uv}^{i-1}, d_{ui}^{i-1} + d_{iv}^{i-1})[/math]. Т.е., если кратчайший путь из [math]u[/math] в [math]v[/math], содержащий только вершины с номерами [math]1 .. i[/math], проходит через вершину [math]i[/math], то пройдём сначала из [math]u[/math] в [math]i[/math], затем из [math]i[/math] в [math]v[/math], иначе ничего менять не будем.

Код (в первом приближении)

 # Инициализация
 d[0] = w
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..n}:
       d[i][u][v] = min(d[i-1][u][v], d[i-1][u][i] + d[i-1][i][v])

Код (окончательный)

Заметим, что для заполнения [math]i[/math]-того слоя массива используются только значения из [math](i-1)[/math]-го слоя. Таким образом, от первого индекса вообще можно отказаться.

 # Инициализация
 d = w
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..n}:
       d[u][v] = min(d[u][v], d[u][i] + d[i][v])

Алгоритм всегда завершит работу за [math]O(V^3)[/math] — как не сложно видеть, три вложенных цикла выполняются по [math]n[/math] раз каждый.

Пример работы

Здесь пример, да

Вывод кратчайшего пути

Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив [math]t_{uv}[/math], в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из [math]u[/math] в [math]v[/math] по кратчайшему пути.

Модифицированный алгоритм

 # Инициализация
 d = w
 t[u][v] = v если есть ребро uv
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..n}:
       if (d[u][i] + d[i][v]) < d[u][v]: 
         d[u][v] = d[u][i] + d[i][v]
         t[u][v] = t[u][i]
 # Вывод кратчайшего пути
 def get_shortest_path(u, v):
   if d[u][v] == inf:
       raise NoPath # Из u в v пути нет
   c = u
   while c != v:
     yield c
     c = t[c][v]
   yield v

Floyd path.png