Хотя обычно достаточно просто понять, что алгоритм принимает в качестве параметров и что он возвращает, часто полезно более глубокое понимание этого. Лично я предпочитаю получить это понимание, выполняя вычисления для примера вручную, так как это заставляет меня действительно понимать каждый шаг алгоритма.
Что такое алгоритм Флойда-Уоршалла
Алгоритм Флойда-Уоршалла — это алгоритм поиска кратчайшего пути в ориентированном взвешенном графе. Алгоритм принимает представление матрицы ориентированного графа в качестве входных данных, а затем обновляет эту матрицу по мере нахождения более коротких путей к каждому узлу. Наконец, он возвращает обновленную матрицу, представляющую кратчайший путь для каждой пары узлов в графе. Ниже можно увидеть алгоритм, реализованный на питоне.
V =
Number of vertices in the graphINF =
99999
def
floydWarshall(graph): dist =
list(map(lambda
i: list(map(lambda
j: j, i)), graph))
for
k in
range(V): for
i in
range(V): for
j in
range(V): dist[i][j] =
min(dist[i][j],dist[i][k] +
dist[k][j])
return dist
Ввод Флойда-Уоршалла
Как видно из алгоритма, входные данные — это просто график, но он несколько неоднозначен, поэтому я покажу и объясню, в какой форме должен быть этот график и как его получить из нормального представления. Входные данные, ожидаемые в приведенном выше алгоритме, представляют собой матрицу, которая по существу представляет собой список списков. Пример этого в python может быть таким:
graph = [[0,INF
,INF
,INF
,-1,INF
], [1
,0,INF
,2,INF
,INF],
[INF
,2,0,INF
,INF,-8],
[-4,INF
,INF
,0,3,INF],
[INF,7,INF
,INF,0,INF],
[INF,5,10,INF,INF,0]
]
Это должна быть форма входа в алгоритм, но в том виде, в каком она есть сейчас, без знания того, как она получена, может показаться чепухой.
График, которому соответствует приведенная выше матрица, можно увидеть здесь:
Теперь, как показанная матрица получена из этого графика?
Чтобы показать это, я предоставлю матрицу с немного большей информацией, а затем пройдусь по каждой строке, чтобы объяснить метод.
Таким образом, единственное отличие от первой матрицы и этой состоит в том, что отсюда можно считывать разные пары.
Теперь, чтобы на самом деле посмотреть, как эта матрица может быть построена, это можно легко сделать построчно. Итак, давайте начнем с первой строки:
[0,INF
,INF
,INF
,-1,INF
]
По сути, это расстояние от узла А до любого другого узла в графе, если разрешен одиночный переход. Традиция от A до A равна 0, потому что мы уже находимся в A, ячейки с записанным INF являются недостижимыми узлами. -1 - это переход от A к E. Вот как строится матрица, я просто возьму еще одну строку:
[1
,0,INF
,2,INF
,INF]
B имеет переход к A с весом 1. Опять же, переход к самому себе всегда будет 0. Не существует перехода от B к C. Существует переход от B к D с весом 2. Остальные INF как не существует единого перехода от B ни к E, ни к F.
Это в основном то, как вы могли бы построить матрицу вручную, теперь к фактическому алгоритму.
Расчеты
Идея состоит в том, что мы берем первую строку и столбец и смотрим, есть ли какие-либо возможные пути короче, чем те, которые уже есть в матрице, и если они есть, мы обновляем матрицу. Затем продолжаем со второй строкой и столбцом.
Теперь я покажу подход с помощью приведенного выше графика. Итак, у нас есть исходная матрица, и мы посмотрим на первую строку и первый столбец, отмеченные оранжевым цветом.
Что мне нравится делать здесь, так это записывать все выбранные пары, так как это делает более систематичным просмотр новых возможных переходов.
(A,E)= -1, (B,A)= 1, (D,A)= -4
Глядя на пары, мы можем увидеть два новых перехода, а именно: от B к E и от D к E. Я обычно записываю это следующим образом:
(B,A)+(A,E)=(B,E)=0, (D,A)+(A,E)=(D,E)=-5
Таким образом, мы обнаружили два новых перехода, которыми мы можем обновить матрицу. Мы также должны заметить, что переход (D,E) уже существует, но поскольку мы нашли новый переход с меньшим весом всего -5, мы переопределим старые значения, поскольку цель состоит в том, чтобы найти кратчайший путь. Обновления выделены голубым цветом.
Следующий шаг будет таким же, но со второй строкой и столбцом, как показано здесь:
Снова находим все пары в выделенных частях:
(B,A)=1, (B,D)=2, (B,E)=0, (C,B)=2, (E,B)=7, (F,B)=5
Теперь ищем новые переходы:
(C,B)+(B,A)=(C,A)=3, (C,B)+(B,D)=(C,D)=3, (C,B)+(B,E)=(C,E)=2, (E,B)+(B,A)=(E,A)=8, (E,B)+(B,D)=(E,D)=9, (F,B)+(B,A)=(F,A)=3, (F,B)+(B,D)=(F,D)=3, (F,B)+(B,E)=(F,E)=7
Здесь было найдено много новых переходов, которые приводят к этой матрице:
При таком подходе для оставшихся строк и столбцов кратчайший путь для каждой пары будет находиться в матрице.