- PVSM.RU - https://www.pvsm.ru -
В предыдущих частях цикла мы рассмотрели алгоритмы DFS [1] и BFS [2], позволяющие найти путь в графе и обладающие рядом других интересных свойств. Но в жизни очень часто оказывается, что гораздо проще выглядит модель задачи в виде графа с неодинаковыми длинами ребер. Поиском кратчайшего пути во взвешенном графе мы и займемся под катом.
В задаче рассматривается взвешенный граф — то есть граф, каждому ребру которого сопоставлено некоторое число, называемое его весом. Вес ребра, ведущего из вершины u в вершину v, мы будем обозначать weight[u, v].
Требуется найти путь из вершины u в вершину v, сумма весов ребер которого минимальна. Эту сумму весов будем называть расстоянием от вершины u до вершины v и обозначать dist[u, v].
В жизни встречается довольно-таки большое количество задач, которые могут быть переформулированы в указанном виде — например, задача определения времени поездки в метро (и оптимального маршрута) при условии наличия штрафов за пересадки.
Рассмотрим какое-нибудь ребро (v, w). Что мы можем сказать про расстояния до его концов? Очевидно, dist[u, w] ≤ dist[u, v] + weight[v, w].
Давайте будем действовать итерационно. Изначально известно расстояние только до начальной вершины — оно равно 0. В каждый момент времени мы можем проверить выполнение свойства для какого-нибудь ребра и, если оно нарушено, улучшить существующую оценку расстояния до конечной вершины ребра. Это процедура называется релаксацией.
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.
В доказательстве не зря была сделана оговорка — ищутся все существующие кратчайшие пути. Существует ситуация, в которой есть путь от u до v, но нет кратчайшего пути от u до v — например, если обе эти вершины входят в цикл отрицательного веса. Это является математическим эквивалентом случая, когда переходы между вершинами — это порталы, причем такие, которые могут забросить как в прошлое, так и в будущее. Присутствие цикла отрицательного веса означает, что пройдя по нему нужное количество оборотов, можно оказаться в прошлом так далеко, как хочется.
Алгоритм Форда-Беллмана предоставляет и способ нахождения таких циклов: если циклов нет — значит, все кратчайшие пути не длиннее, чем из V — 1 ребра, и на последней итерации не будет произведено ни одной релаксации. Все ребра, релаксация которых производилась на последней итерации, лежат в циклах отрицательного веса, достижимых из начальной верщины.
Автор: alexeykuzmin0
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/47982
Ссылки в тексте:
[1] DFS: http://habrahabr.ru/post/200074/
[2] BFS: http://habrahabr.ru/post/200252/
[3] Источник: http://habrahabr.ru/post/201588/
Нажмите здесь для печати.