В предыдущих частях цикла мы рассмотрели алгоритмы 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 ребра, и на последней итерации не будет произведено ни одной релаксации. Все ребра, релаксация которых производилась на последней итерации, лежат в циклах отрицательного веса, достижимых из начальной верщины.