![](http://habr.habrastorage.org/post_images/f63/d61/163/f63d611631148114b41bb3f0472f304b.gif)
Постановка задачи
В задаче рассматривается взвешенный граф — то есть граф, каждому ребру которого сопоставлено некоторое число, называемое его весом. Вес ребра, ведущего из вершины 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.
- База: 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 ребра, и на последней итерации не будет произведено ни одной релаксации. Все ребра, релаксация которых производилась на последней итерации, лежат в циклах отрицательного веса, достижимых из начальной верщины.
ссылка на оригинал статьи http://habrahabr.ru/post/201588/
Добавить комментарий