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

Дан ориентированный взвешенный граф с $n$ вершинами и $m$ ребрами. И задана некоторая вершина $s$.

Требуется найти длины кратчайших путей от вершины $s$ до всех остальных.

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

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

Решим задачу с помощью динамического программирования по стандартному плану:

• Сформулировать, что будет хранить каждое состояние.

  $dp[k][v]$ - длина кратчайшего пути из вершины $s$ до вершины $v$, содержащего не более $k$ ребер.

• Найти формулу перехода.

  Попробуем пройти из всех вершин с путем, содержащим не более $k - 1$ ребра.

  $dp[k][v] = dp[k - 1][u] + w[u][v]$.

• Определить порядок пересчета.

  Слои нужно заполнять по увеличению $k$ для каждой из вершин $v$.

• Задать значения базы динамики.

  $dp[k][v] = \infty$

  $dp[0][s] = 0$

• Понять, где лежит ответ.

  $dp[k]$ - последний слой содержит ответ на задачу.

Заметим, что можно не хранить все слои динамики, а обойтись только последним, причем пересчитывать его можно прямо на “месте”.

vector<int> dp(n, INF);
dp[s] = 0;

for (int k = 1; k < n; ++k)
    for (int v = 0; v < n; ++v)
         for (int u = 0; u < n; ++u)
                 dp[v] = min(dp[v], dp[u] + w[u][v]);

Итоговая асимптотика - $O(n^3)$.

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

Если есть цикл отрицательного веса, достижимый из $s$, то сделав еще одну ($n + 1$ по счету) итерацию, мы сможем улучшить ответ (т.к. на цикле отрицательного веса можно найти бесконечно короткий путь).

Чтобы его восстановить, сохраним номер вершины для которой обновился ответ. Она лежит на цикле или цикл из нее достижим. Пройдем из этой вершины по предкам $n$ раз, тогда мы точно окажемся в вершине на цикле. Из этой вершины по массиву предков легко восстановить сам цикл.

int v0 = -1;
for (int v = 0; v < n; ++v) {
    for (int u = 0; u < n; ++u) {
        if (dp[u] + w[u][v] < dp[v]) {
            dp[v] = dp[u] + w[u][v];
            v0 = v;
        }
    }
}

if (v0 != -1) {
    for(int _ = 0; _ < n; ++_) {
        v0 = p[v0];
    }
    
    vector<int> cycle;
    do {
        cycle.push_back(v0);
        v0 = p[v0];
    } while (v0 != cycle.front());
    
    reverse(cycle.begin(), cycle.end());
}

Идеи для улучшения

• аккуратнее с переполнением. Возможно, нужно сделать что-то вроде max(-INF, dp[..]), если в графе много больших ребер отрицательного веса и они образуют цикл.
• если на очередном слое $k$ никакие расстояния не поменялись, то алгоритм можно закончить раньше
• сохраним граф в виде списка ребер. Тогда асимптотика - $O(nm)$, что может быть лучше для разреженных графов.
• если случайно перемешать в начале список ребер, то алгоритм скорее всего будет эффективнее (доказывать мы это не будем, но этот несложный факт может спасти вас от TL на олимпиаде)

Алгоритм Флойда

Этот алгоритм ищет в графе расстояние между всеми парами вершин. Единственное ограничение - отсутствие отрицательных циклов.

Он работает с помощью динамического программирования, заполняя массив $dp[u][v][i]$ - кратчайшее расстояние между $u$ и $v$, если помимо $u$, $v$ можно использовать лишь вершины с номерами $1..i$.

База динамики - $dp[u][v][0] = w[u][v]$, где $w[u][v]$ - величина ребра между $u$ и $v$ или $+\infty$, если такого ребра нет. Остальные значения заполняем $+\infty$.

Для пересчёта динамики будем добавлять вершины по порядку: когда мы добавлем вершину $i$, у нас уже посчитаны $dp[u][v][i - 1]$, и тогда для произвольной пары $u$, $v$ верно $dp[u][v][i] = min(dp[u][v][i - 1], dp[u][i][i - 1] + dp[i][v][i - 1])$. Действительно: путь $u \rightarrow v$ на первых $i$ вершинах либо проходит через $i$, либо содержит только первые $i - 1$ вершину, значит, пересчёт корректен.

Когда мы добавим все вершины, $dp[u][v][n]$ и будет искомой матрицей расстояний.

Оптимизация памяти

Оказывается, можно не использовать размерность $i$ в массиве $d$ и только лишь обновлять один и тот же слой. Тогда формула пересчёта примет следующий вид: $dp[u][v][i] = min(dp[u][v], dp[u][i] + dp[i][v])$

Восстановление путей

Для того, чтобы восстанавливать кратчайший путь, можно создать массив $next[u][v]$, в котором будет храниться следующая вершина, в которую нужно пойти из $u$, чтобы прийти в $v$. Изначально $next[u][v] = v$, если и только если есть ребро $u \rightarrow v$.

Код

...  // там происходит инициализация d и w
for (int i = 0; i < n; ++i) {
    for (int u = 0; u < n; ++u) {
        for (int v = 0; v < n; ++v) {
            if (d[u][i] + d[i][v] < d[u][v]) {
                d[u][v] = d[u][i] + d[i][v];
                next[u][v] = next[u][i];
            }
        }
    }
}

Отрицательные циклы

Можно доказать, что в графе есть отрицательные циклы тогда и только тогда, когда $d[v][v] < 0$ для какого-нибудь $v$, причём $v$ в таком случае лежит на отрицательном цикле. Поэтому для поиска отрицательных циклов можно пользоваться этим свойством.

Если в графе есть отрицательные циклы, то значения $d$ могут экспоненциально расти по модулю, из-за чего возможны переполнения. Для их избежания надо или ограничивать все значения снизу $-\infty$, или выполнять проверку на отрицательные циклы в процессе алгоритма и завершать работу, если такие есть.

Асимптотика

Очевидно, что алгоритм имеет асимптотику $O(n^3)$ по времени и $O(n^2)$ по памяти.