Алгоритмы Флойда-Уоршелла и Форда-Беллмана

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

Алгоритм Флойда-Уоршелла позволяется за \({\cal{O}}(n^3)\) по времени и \({\cal{O}}(n^2)\) по памяти найти кратчайшие пути между всеми парами вершин в графе. Веса ребер при этом могут иметь произвольный вес (не обязательно неотрицательный).

Изначально граф задан матрицей смежности. Если ребра между вершинами нет, то запишем в эту ячейку \(\infty\). На диагонали будут стоять нули, так как считаем, что петель в графе нет. Теперь будем постепенно преобразовывать матрицу смежности в матрицу расстояний:

floyd(weights_matrix):
    dists = weights_matrix
    for i ∈ V:
        for u ∈ V:
            for v ∈ V:
                dists[u][v] = min(dists[u][v], dists[u][i] + dists[i][v]) // "релаксация"

Чтобы определять не только длину кратчайшего пути, то и восстанавливать его, можно воспользовать уже хорошо известным нам приемом с запоминанием дополнительной информации. Будем хранить двумерный массив, где для каждой пары вершин хранится вторая вершина их кратчайшего пути. Изначально \(second[u][v] = v\). Затем заполняем \(second[u][v] = second[u][i]\), если происходит “релаксация” через вершину \(i\)

Затем по этому двумерному массиву можно за линейную сложность восстанавливать кратчайший путь между любыми вершинами.

Цикл отрицательного веса

Если веса могут отрицательными, то в графе можно встретить цикл, сумма весов ребер которого будет отрицательной. Часто нам нужно определять, если ли такой цикл в графе. После получения матрицы расстояний по алгоритму Флойда-Уоршелла можно: если на диагонали такой матрицы встречается отрицательное число, то цикл отрицательного веса точно есть и он включает в себя эту вершину. Восстановить такой цикл можно таким же образом, как и обыкновенный путь.

Алгоритм Форда-Беллмана

Если алгоритм Дейкстры позволяет находить кратчайшие пути от одной вершины для всех в графе с неотрицательными весами, то алгоритм Форда-Беллмана позволяет решать ту же задачу, но без ограничений на неотрицательность весов. Важно отметить, что могут возникать циклы отрицательного веса, которые достижимы из начальной вершины, алгоритм Форда-Беллмана умеет корректно их обрабатывать.

Идея в том, что мы совершаем \(V - 1\) шаг, на каждом шаге мы дополняем кратчайшие пути длины \(k\) до кратчайших путей длины \(k + 1\) (длины здесь считаем в ребрах).

Количество путей длины \(k\) рёбер можно найти с помощью метода динамического программирования.

Пусть \(d[k][u]\) — количество путей длины \(k\) рёбер, которые заканчиваются в вершине \(u\). Тогда рекуррентное соотношение имеет вид: \[ d[k][u] = \sum\limits_{v:\; vu \in E} d[k-1][v] \] То есть, для подсчёта количества путей длины \(k\) до \(u\), нужно для каждого входящего в \(u\) ребра \(vu\) взять сумму по всем вершинам \(v\) числа путей длины \(k-1\) до этих \(v\).

Аналогично можно посчитать минимальный вес пути длины ровно \(k\) рёбер. Пусть \(s\) — стартовая вершина. Определим \(d[k][u]\) как минимальный вес пути длины \(k\) рёбер, заканчивающегося в вершине \(u\). Тогда:

\[ d[0][s] = 0, \qquad d[0][u] = +\infty \; \text{для } u \ne s \]

и далее:

\[ d[k][u] = \min\limits_{v:\; vu \in E} \big( d[k-1][v] + \omega(u, v) \big) \]

где \(\omega(u, v)\) — вес ребра из \(v\) в \(u\).

bool fordBellman(s):
    for v ∈ V:
        d[v] = 1
    d[s] = 0
    for i = 0 to |V|−1: // выполняем V - 1 шаг. На каждом шаге построены все пути длины не больше k в ребрах
        for (u,v) ∈ E: // в отличие от Дейкстры, приходится перебирать ВСЕ ребра
            if d[v] > d[u] + ω(u,v): // стандартная релаксация для каждого ребра
                // ω(u,v) — вес ребра uv
                d[v] = d[u] + ω(u,v)
                  
    // осталось проверить, если ли цикл отрицательного веса
    // такой есть, если уже после построения всех путей еще происходят релаксации
    for (u,v) ∈ E:
        if d[v] > d[u] + ω(u,v):
            return false
    return true