Pull to refresh

Графы для самых маленьких: Ford & Bellman или как понять, что ты попал в бесконечно далекое прошлое

Reading time3 min
Views59K
В предыдущих частях цикла мы рассмотрели алгоритмы DFS и BFS, позволяющие найти путь в графе и обладающие рядом других интересных свойств. Но в жизни очень часто оказывается, что гораздо проще выглядит модель задачи в виде графа с неодинаковыми длинами ребер. Поиском кратчайшего пути во взвешенном графе мы и займемся под катом.

Постановка задачи

В задаче рассматривается взвешенный граф — то есть граф, каждому ребру которого сопоставлено некоторое число, называемое его весом. Вес ребра, ведущего из вершины u в вершину v, мы будем обозначать weight[u, v].
Требуется найти путь из вершины u в вершину v, сумма весов ребер которого минимальна. Эту сумму весов будем называть расстоянием от вершины u до вершины v и обозначать dist[u, v].

В жизни встречается довольно-таки большое количество задач, которые могут быть переформулированы в указанном виде — например, задача определения времени поездки в метро (и оптимального маршрута) при условии наличия штрафов за пересадки.

Давайте придумаем что-нибудь простое

Рассмотрим какое-нибудь ребро (v, w). Что мы можем сказать про расстояния до его концов? Очевидно, dist[u, w] ≤ dist[u, v] + weight[v, w].
Доказательство
Пусть dist[u, v] = K. Это значит, что существует путь от u до v весом K. Добавим к этому пути ребро (v, w). Получим путь от u до w весом K + weight[v, w]. Так как расстояние от u до w — минимальная из длин всех путей, соединяющих u и v, dist[u, w] ≤ K + weight[v, w]

Давайте будем действовать итерационно. Изначально известно расстояние только до начальной вершины — оно равно 0. В каждый момент времени мы можем проверить выполнение свойства для какого-нибудь ребра и, если оно нарушено, улучшить существующую оценку расстояния до конечной вершины ребра. Это процедура называется релаксацией.

Слова ничто, покажите мне код!

Ford & Bellman algorithm
В коде предполагается, что граф хранится в vector<vector<pair<int, int>>> edges, где edges[v] — вектор всех ребер, исходящих из вершины v. В ребре edges[v][i] первое поле — конечная вершина ребра, второе — его вес. INF — это некоторая константа, заведомо большая, чем любое получающееся расстояние. Обозначает отсутствие известного пути.
void ford_bellman(int start)
{
    // Инициализация
    for (int i = 0; i < (int)edges.size(); ++i)
    {
        dist[i] = INF;
    }
    dist[start] = 0;
    // V раз релаксируем все ребра
    for (int iter = 0; iter < (int)edges.size(); ++iter)
    {
        // Перебираем начало ребра
        for (int v = 0; v < (int)edges.size(); ++v)
        {
            // Перебираем само ребро
            for (int i = 0; i < (int)edges[v].size(); ++i)
            {
                // Если нужно
                if (dist[edges[v][i].first] > dist[v] + edges[v][i].second)
                {
                    // Обновляем расстояние
                    dist[edges[v][i].first] = dist[v] + edges[v][i].second;
                }
            }
        }
    }
}


Как много ресурсов надо алгоритму?

Помимо графа и значений, выдающихся в ответ, мы храним лишь константное количество памяти, следовательно, количество памяти, требующееся алгоритму — O(1) + <память на хранение графа и ответа> = O(V + E) = O(E).
Релаксация каждого ребра занимает константное количество действий. Всего ребер — E, релаксация всех ребер производится V раз. Таким образом, временная сложность алгоритма — O(VE).

А если я педант?

Давайте докажем, что после k итераций алгоритм найдет все кратчайшие пути, состоящие из k ребер или менее. Тогда получится, что в конце работы он найдет все кратчайшие пути из не более, чем V ребер — то есть, все существующие кратчайшие пути.
Для удобства обозначим начальную вершину u.
  • База: k = 0 очевидно, путь из начальной вершины в нее же найден верно
  • Предположение: после k итераций для всех вершин v, до которых существует кратчайший путь, состоящий из не более, чем k ребер, dist[v] равно расстоянию от начальной вершины до v
  • Шаг: рассмотрим некоторую вершину w, до которой существует кратчайший путь, состоящий из k + 1 ребра.
    • Обозначим предпоследнюю вершину в пути от u до w, как v.
    • Для v существует кратчайший путь из k вершин (например, начало кратчайшего пути до w).
    • Значит, кратчайший путь до v был найден на предыдущей итерации. Проведя релаксацию ребра (v, w) на k + 1-ой итерации, мы получим верное значение расстояния до вершины w.
    • Заметим, что при релаксации какого-либо другого ребра мы не могли получить значения, меньшего, чем верное расстояние, поскольку каждой релаксации ребра (x, w) можно поставить в соответствие путь из начальной вершины в w соответствующей длины.

А как же путешествия во времени?

В доказательстве не зря была сделана оговорка — ищутся все существующие кратчайшие пути. Существует ситуация, в которой есть путь от u до v, но нет кратчайшего пути от u до v — например, если обе эти вершины входят в цикл отрицательного веса. Это является математическим эквивалентом случая, когда переходы между вершинами — это порталы, причем такие, которые могут забросить как в прошлое, так и в будущее. Присутствие цикла отрицательного веса означает, что пройдя по нему нужное количество оборотов, можно оказаться в прошлом так далеко, как хочется.
Алгоритм Форда-Беллмана предоставляет и способ нахождения таких циклов: если циклов нет — значит, все кратчайшие пути не длиннее, чем из V — 1 ребра, и на последней итерации не будет произведено ни одной релаксации. Все ребра, релаксация которых производилась на последней итерации, лежат в циклах отрицательного веса, достижимых из начальной верщины.
Tags:
Hubs:
Total votes 30: ↑27 and ↓3+24
Comments5

Articles