Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

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

Разберём алгоритм на примере:

Пусть дан следующий граф:

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  ABCD-112-2-54

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

Изначально все расстояния принимаются за бесконечность.

Расстояние из i-ой вершины в саму себя устанавливается на 0.

Также устанавливаются расстояния между соседними вершинами, равные весу соединяющего их ребра.

Теперь для пары вершин $(i, j)$ необходимо пересчитать кратчайшее расстояние через третью вершину k:

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]))$,

Где: $dist[X][Y]$- расстояние из вершины X в вершину Y; i, j, k - любые вершины в графе; i, j и k могут совпадать.

Кратчайшее расстояние из $i$ в $j$: $min(t, a + b)$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[A][A], dist[A][A] + dist[A][A]) = min(0, 0 + 0) = 0$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[A][B], dist[A][A] + dist[A][B]) = min(-1, 0 + -1) = -1$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[A][C], dist[A][A] + dist[A][C]) = min(1, 0 + 1) = 0$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[A][D], dist[A][A] + dist[A][D]) = min(4, 0 + 4) = 4$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[B][A], dist[B][A] + dist[A][A]) = min(∞, ∞ + 0) = ∞$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[B][B], dist[B][A] + dist[A][B]) = min(0, ∞ + -1) = 0$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[B][C], dist[C][A] + dist[A][B]) = min(2, ∞ + -1) = 2$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[B][D], dist[D][A] + dist[A][B]) = min(-2, ∞ + -1) = -2$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[C][A], dist[C][A] + dist[A][A]) = min(∞, ∞ + 0) = ∞$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[C][B], dist[C][A] + dist[A][B]) = min(∞, ∞ + -1) = ∞$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[C][C], dist[C][A] + dist[A][C]) = min(0, ∞ + 1) = 0$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[C][D], dist[C][A] + dist[A][D]) = min(-5, ∞ + 4) = -5$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[C][D], dist[C][A] + dist[A][D]) = min(-5, ∞ + 4) = -5$

$dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) = min(dist[D][A], dist[D][A] + dist[A][A]) = min(∞, ∞ + 0) = ∞$

Итерация для k = A закончилась, матрица кратчайших расстояний выглядит так:

Далее необходимо произвести те же действия для k = B, C, D.

После итерации k = B изменилось кратчайшее расстояние из A в D:

После итерации k = С изменились кратчайшие расстояния из A в D и из B в D:

После итерации k = D матрица кратчайших расстояний не изменилась:

Если в матрице кратчайших расстояний на её главной диагонали присутствуют элементы меньшие нуля, то в данном графе существует отрицательный цикл.

---

Вычислительная сложность

Временная сложность - $O(V^3)$, пространственная - $O(V^2)$, где $V$ - множество вершин графа.

---

Псевдокод

Аннотация:
FloydWarshell - алгоритм Флойда-Уоршелла
graph - матрица смежности, в которой хранится граф
vertexes - список вершин графа
dist - матрица расстояний, заполненная бесконечностями

Функция FloydWarshell(graph)
    для вершины i в vertexes
        dists[i][i] <- 0

        для вершины j в vertexes
            если graph[i][j] это не бесконечность
                dists[i][j] <- graph[i][j]

    для вершины k в vertexes
        для вершины i в vertexes
            для вершины j в vertexes
                dist[i][j] <- минимум(dist[i][j], dist[i][k] + dist[k][j])

    вернуть dist

---

Реализация на Python

Аннотация:
floyd_warshall - алгоритм Флойда-Уоршелла
graph - матрица смежности, в которой хранится граф
vertexes - количество вершин в графе
dists - матрица кратчайших расстояний между всеми парами вершин
inf - бесконечность, используемая для инициализации матрицы расстояний
isfinite - функция из модуля math для проверки конечности значения

def floyd_warshall(graph):
    vertexes = len(graph)
    dists = [[float('inf')] * v for _ in range(v)]

    for i in range(v):
        dists[i][i] = 0
        for j in range(v):
            if math.isfinite(graph[i][j]):
                dists[i][j] = graph[i][j]

    for k in range(v):
        for i in range(v):
            for j in range(v):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])

    return dists

---

Олимпиадная реализация на С++

Аннотация:
typedef - переопределение имени типа данных
floyd - алгоритм Флойда-Уоршелла
v - количество вершин в графе
d - инициализация диагональных элементов матрицы расстояний

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

const int INF = numeric_limits<int>::max();

vvi floyd(vvi& g) {
    auto v = g.size();
    vvi d(v, vi(v, INF));

    for (int i = 0; i < v; ++i) {
        d[i][i] = 0;
        for (int j = 0; j < v; ++j)
            if (g[i][j] != INF)
                d[i][j] = g[i][j];
    }

    for (int k = 0; k < v; ++k)
        for (int i = 0; i < v; ++i)
            for (int j = 0; j < v; ++j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    return d;
}

---

Продуктовая реализация на С++

Аннотация:
floyd_warshall - алгоритм Флойда-Уоршелла
vertexes - количество вершин в графе
distances - матрица расстояний, инициализированная бесконечностями

const int INF = std::numeric_limits<int>::max();

std::vector<std::vector<int>> floyd_warshall(
                            const std::vector<std::vector<int>> &graph) {
    auto vertexes = vertexes();
    std::vector<std::vector<int>> distances(vertexes, std::vector<int>(vertexes, INF));

    for (int v1 = 0; v1 < vertexs; ++v1) {
        distances[v1][v1] = 0;
        for (int v2 = 0; v2 < vertexes; ++v2)
            if (graph[v1][v2] != INF)
                distances[v1][v2] = graph[v1][v2];
    }

    for (int v1 = 0; v1 < vertexes; ++v1)
        for (int v2 = 0; v2 < vertexes; ++v2)
            for (int v3 = 0; v3 < vertexes; ++v3)
                distances[v2][v3] = std::min(distances[v2][v3], 
                                           distances[v2][v1] + distances[v1][v3]);

    return distances;
}