Хотя обычно достаточно просто понять, что алгоритм принимает в качестве параметров и что он возвращает, часто полезно более глубокое понимание этого. Лично я предпочитаю получить это понимание, выполняя вычисления для примера вручную, так как это заставляет меня действительно понимать каждый шаг алгоритма.

Что такое алгоритм Флойда-Уоршалла

Алгоритм Флойда-Уоршалла — это алгоритм поиска кратчайшего пути в ориентированном взвешенном графе. Алгоритм принимает представление матрицы ориентированного графа в качестве входных данных, а затем обновляет эту матрицу по мере нахождения более коротких путей к каждому узлу. Наконец, он возвращает обновленную матрицу, представляющую кратчайший путь для каждой пары узлов в графе. Ниже можно увидеть алгоритм, реализованный на питоне.

V = Number of vertices in the graph
INF = 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

Здесь было найдено много новых переходов, которые приводят к этой матрице:

При таком подходе для оставшихся строк и столбцов кратчайший путь для каждой пары будет находиться в матрице.