Бюрократы, editor, Администраторы
422
правки
Изменения
Почти готово. Осталось добавить пример
== Алгоритм ==
[[Файл:Floyd.png|right|thumb|Текущий (синий) путь и потенциально более короткий (красный)]]
Пусть дан граф <tex>G(V,E)</tex>; <tex>\omega_{uv} =
\begin{cases}
Обозначим длину кратчайшего пути между вершинами <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>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]]
