E034. Bellman-Ford algorithm

e-maxx algorithm original: C/C++ #algorithm #emaxx #graph #shortest-path

题目文本会按所选界面语言从俄语翻译；代码保持不变。

Static

Источник: e-maxx.ru/algo, страница PDF 107.

Пусть дан ориентированный взвешенный 图

с

vertexми и

рёбрами, и указана некоторая vertex

. it is required find длины кратчайших путей от вершины

до всех остальных вершин. В отличие от 算法а Дейкстры, этот 算法 применим также и к 图ам, содержащим рёбра отрицательного веса. Впрочем, если 图 содержит отрицательный цикл, то, понятно, кратчайшего пути до некоторых вершин может не существовать (по причине того, что вес кратчайшего пути должен быть равен минус бесконечности); впрочем, этот 算法 можно модифицировать, чтобы он сигнализировал о наличии цикла отрицательного веса, или даже выводил сам этот цикл. 算法 носит имя двух американских учёных: Ричарда Беллмана (Richard Bellman) и Лестера Форда (Lester Ford). Форд фактически изобрёл этот 算法 в 1956 г. при изучении другой математической задачи, под题目 которой свелась к поиску кратчайшего пути в 图е, и Форд дал набросок решающего эту задачу 算法а. Беллман в 1958 г. опубликовал статью, посвящённую конкретно задаче нахождения кратчайшего пути, и в этой статье он чётко сформулировал 算法 в том виде, в котором он известен нам сейчас.

Описание 算法а

Мы считаем, что 图 не содержит цикла отрицательного веса. Случай наличия отрицательного цикла будет рассмотрен ниже в отдельном разделе.

Заведём 数组 расстояний

, который после отработки 算法а будет содержать ответ на задачу. В начале работы мы заполняем его следующим образом:

, а все остальные elementы

равны

бесконечности

. Сам Bellman-Ford algorithm представляет из себя несколько фаз. На каждой фазе просматриваются все рёбра 图а, и 算法 пытается произвести релаксацию (relax, ослабление) вдоль каждого ребра

стоимости

. Релаксация вдоль ребра — это попытка улучшить значение

значением

. Фактически это значит, что

мы пытаемся улучшить ответ для вершины

, пользуясь edgeм

и текущим ответом для вершины

Утверждается, что достаточно

фазы 算法а, чтобы корректно посчитать длины всех кратчайших путей в 图е (повторимся, мы считаем, что циклы отрицательного веса отсутствуют). Для недостижимых вершин расстояние

останется равным бесконечности

实现

Для 算法а Форда-Беллмана, в отличие от многих других 图овых 算法ов, более удобно представлять 图

в виде одного списка всех рёбер (а не

списков рёбер — рёбер из каждой вершины). В приведённой

реализации заводится структура данных

для ребра. 输入ными данными для 算法а являются числа

, список

рёбер, и номер стартовой вершины

. Все номера вершин нумеруются с

по

Простейшая 实现

Константа

обозначает number "бесконечность" — её надо подобрать таким образом, чтобы она заведомо превосходила все возможные длины путей.

struct edge {

int a, b, cost;

};

int n, m, v;

vector<edge> e;

const int INF = 1000000000;

void solve() {

vector<int> d (n, INF);

d[v] = 0;

for (int i=0; i<n-1; ++i)

for (int j=0; j<m; ++j)

if (d[e[j].a] < INF)

d[e[j].b] = min (d[e[j].b], d[e[j].a] + e

[j].cost);

// вывод d, на示例, на экран

} Проверка "if (d[e[j].a] < INF)" нужна, только если 图 содержит рёбра отрицательного веса: без такой проверки бы происходили релаксации из вершин, до которых пути ещё не нашли, и появлялись бы некорректные расстояния

вида

,

, и т.д.

Улучшенная 实现

Этот 算法 можно несколько ускорить: зачастую ответ находится уже за несколько фаз, а оставшиеся фазы никакой полезной работы не происходит, лишь впустую просматриваются все рёбра. Поэтому будем хранить флаг того, изменилось что-то на текущей фазе или нет, и если на какой-то фазе ничего не произошло, то 算法 можно останавливать. (Эта оптимизация не улучшает асимптотику, т.е. на некоторых 图ах по-прежнему будут нужны

все

фаза, но значительно ускоряет поведение 算法а "в среднем", т.е. на случайных 图ах.) С такой оптимизацией становится вообще ненужным ограничивать вручную number фаз 算法а numberм

— он

сам остановится через нужное number фаз.

void solve() {

vector<int> d (n, INF);

d[v] = 0;

for (;;) {

bool any = false;

for (int j=0; j<m; ++j)

if (d[e[j].a] < INF)

if (d[e[j].b] > d[e[j].a] + e[j].cost) {

d[e[j].b] = d[e[j].a] + e[j].cost;

any = true;

}

if (!any)  break;

}

// вывод d, на示例, на экран

}

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

Рассмотрим теперь, как можно модифицировать Bellman-Ford algorithm так, чтобы он не только находил длины кратчайших путей, но и позволял восстанавливать сами кратчайшие пути.

Для этого заведём ещё один 数组

, в котором для каждой вершины будем хранить её "предка", т. е. предпоследнюю вершину в кратчайшем пути, ведущем в неё. В самом деле, 最短路径 до какой-то вершины

является кратчайшим путём до какой-то вершины

, к которому приписали в конец вершину

. Заметим, что Bellman-Ford algorithm работает по такой же логике: он, предполагая, что кратчайшее расстояние до одной вершины уже посчитано, пытается улучшить кратчайшее расстояние до другой вершины. Следовательно,

в момент улучшения нам надо просто запоминать в

, из какой вершины это улучшение произошло. Приведём реализацию Форда-Беллмана с восстановлением пути до какой-то заданной вершины :

void solve() {

vector<int> d (n, INF);

d[v] = 0;

vector<int> p (n, -1);

for (;;) {

bool any = false;

for (int j=0; j<m; ++j)

if (d[e[j].a] < INF)

if (d[e[j].b] > d[e[j].a] + e[j].cost) {

d[e[j].b] = d[e[j].a] + e[j].cost;

p[e[j].b] = e[j].a;

any = true;

}

if (!any)  break;

}

if (d[t] == INF)

cout << "No path from " << v << " to " << t << ".";

else {

vector<int> path;

for (int cur=t; cur!=-1; cur=p[cur])

path.push_back (cur);

reverse (path.begin(), path.end());

cout << "Path from " << v << " to " << t << ": ";

for (size_t i=0; i<path.size(); ++i)

cout << path[i] << ' ';

} }

Здесь мы сначала проходимся по предкам, начиная с вершины

, и сохраняем весь пройденный путь в списке

В этом списке получается 最短路径 от

до

, но в обратном порядке, поэтому мы вызываем

от него

и затем выводим.

证明算法а

Во-первых, сразу заметим, что для недостижимых из

вершин 算法 отработает корректно: для них метка

так

и останется равной бесконечности (т.к. Bellman-Ford algorithm найдёт какие-то пути до всех достижимых из

вершин, а релаксация во всех остальных vertexх не произойдёт ни разу).

Докажем теперь следующее утверждение: после выполнения

фаз Bellman-Ford algorithm корректно

находит все кратчайшие пути, длина которых (по числу рёбер) не превосходит .

Иными словами, для любой вершины

обозначим через

number рёбер в кратчайшем пути до неё (если таких

путей несколько, можно взять любой). Тогда это утверждение говорит о том, что после

фаз этот 最短路径

будет найден гарантированно.

证明. Рассмотрим произвольную вершину

, до которой существует путь из стартовой вершины

,

и рассмотрим 最短路径 до неё:

. Перед первой фазой 最短路径

до вершины

найден корректно. Во время первой фазы edge

было просмотрено 算法ом

Форда-Беллмана, следовательно, расстояние до вершины

было корректно посчитано после первой фазы.

Повторяя эти утверждения

раз, получаем, что после

-й фазы расстояние до вершины

посчитано

корректно, что и требовалось доказать. Последнее, что надо заметить — это то, что любой 最短路径 не может иметь более ребра.

Следовательно, 算法у достаточно произвести только

фазу. После этого ни одна релаксация

гарантированно не может завершиться улучшением расстояния до какой-то вершины.

Случай отрицательного цикла

Выше мы везде считали, что отрицательного цикла в 图е нет (уточним, нас интересует отрицательный

цикл, достижимый из стартовой вершины

, а недостижимые циклы ничего в вышеописанном 算法е не меняют). При его наличии возникают дополнительные сложности, связанные с тем, что расстояния до всех вершин на этом цикле, а также расстояния до достижимых из этого цикла вершин не определены — они должны быть равны минус бесконечности. Нетрудно понять, что Bellman-Ford algorithm сможет бесконечно делать релаксации среди всех вершин этого цикла и вершин, достижимых из него. Следовательно, если не ограничивать number фаз numberм

,

то 算法 будет работать бесконечно, постоянно улучшая расстояния до этих вершин. Отсюда мы получаем критерий наличия достижимого цикла отрицательного веса: если

после

фазы мы выполним ещё одну фазу, и на ней произойдёт хотя бы одна релаксация, то 图 содержит

цикл отрицательного веса, достижимый из

; в противном случае, такого цикла нет. Более того, если такой цикл обнаружился, то Bellman-Ford algorithm можно модифицировать таким образом, чтобы он выводил сам этот цикл в виде последовательности вершин, 输入ящих в него. Для этого достаточно запомнить

номер вершины

, в которой произошла релаксация на

-ой фазе. Эта vertex будет либо лежать на

цикле отрицательного веса, либо она достижима из него. Чтобы получить вершину, которая гарантированно лежит

на цикле, достаточно, на示例,

раз пройти по предкам, начиная от вершины

. Получив номер

вершины,

лежащей на цикле, надо пройтись от этой вершины по предкам, пока мы не вернёмся в эту же вершину

(а

это обязательно произойдёт, потому что релаксации в цикле отрицательного веса происходят по кругу). 实现:

void solve() {

vector<int> d (n, INF);

d[v] = 0;

vector<int> p (n, -1);

int x;

for (int i=0; i<n; ++i) {

x = -1;

for (int j=0; j<m; ++j)

if (d[e[j].a] < INF)

if (d[e[j].b] > d[e[j].a] + e[j].cost) {

d[e[j].b] = max (-INF, d[e[j].a] + e

[j].cost);

p[e[j].b] = e[j].a;

x = e[j].b;

} }

if (x == -1)

cout << "No negative cycle from " << v;

else {

int y = x;

for (int i=0; i<n; ++i)

y = p[y];

vector<int> path;

for (int cur=y; ; cur=p[cur]) {

path.push_back (cur);

if (cur == y && path.size() > 1)  break;

}

reverse (path.begin(), path.end());

cout << "Negative cycle: ";

for (size_t i=0; i<path.size(); ++i)

cout << path[i] << ' ';

} }

Поскольку при наличии отрицательного цикла за

итераций 算法а расстояния могли уйти далеко в минус (по

всей видимости, до отрицательных чисел порядка

), в коде приняты дополнительные меры против

такого целочисленного переполнения:

d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost);

В приведённой выше реализации ищется отрицательный цикл, достижимый из некоторой стартовой вершины

;

однако 算法 можно модифицировать, чтобы он искал просто любой отрицательный цикл в 图е.

Для этого надо положить все расстояния

равными нулю, а не бесконечности — так, как будто бы мы

ищем 最短路径 изо всех вершин одновременно; на корректность обнаружения отрицательного цикла это не повлияет. Дополнительно на тему этой задачи — см. отдельную статью "Поиск отрицательного цикла в 图е".

Задачи в online judges

Список задач, которые можно решить с помощью 算法а Форда-Беллмана:

● E-OLIMP #1453 "Форд-Беллман" [Complexity: низкая]

● UVA #423 "MPI Maelstrom" [Complexity: низкая]

● UVA #534 "Frogger" [Complexity: средняя]

● UVA #10099 "The Tourist Guide" [Complexity: средняя]

● UVA #515 "King" [Complexity: средняя]

См. также список задач в статье "Поиск отрицательного цикла".

C# 解法

自动草稿，提交前请检查

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct edge {
            int a, b, cost;
    };
    int n, m, v;
    vector<edge> e;
    const int INF = 1000000000;
    void solve() {
            List<int> d (n, INF);
            d[v] = 0;
            for (int i=0; i<n-1; ++i)
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    d[e[j].b] = min (d[e[j].b], d[e[j].a] + e
    [j].cost);
            // вывод d, например, на экран
    }
    void solve() {
            List<int> d (n, INF);
            d[v] = 0;
            for (;;) {
                    bool any = false;
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                            d[e[j].b] = d[e[j].a] + e[j].cost;
                                            any = true;
                                    }
                    if (!any)  break;
            }
            // вывод d, например, на экран
    }
    void solve() {
            List<int> d (n, INF);
            d[v] = 0;
            List<int> p (n, -1);
            for (;;) {
                    bool any = false;
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                            d[e[j].b] = d[e[j].a] + e[j].cost;
                                            p[e[j].b] = e[j].a;
                                            any = true;
                                    }
                    if (!any)  break;
            }
            if (d[t] == INF)
                    Console.WriteLine( "No path from " << v << " to " << t << ".";
            else {
                    List<int> path;
                    for (int cur=t; cur!=-1; cur=p[cur])
                            path.push_back (cur);
                    reverse (path.begin(), path.end());
                    Console.WriteLine( "Path from " << v << " to " << t << ": ";
                    for (size_t i=0; i<path.size(); ++i)
                            Console.WriteLine( path[i] << ' ';
            }
    }
    void solve() {
            List<int> d (n, INF);
            d[v] = 0;
            List<int> p (n, -1);
            int x;
            for (int i=0; i<n; ++i) {
                    x = -1;
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                            d[e[j].b] = max (-INF, d[e[j].a] + e
    [j].cost);
                                            p[e[j].b] = e[j].a;
                                            x = e[j].b;
                                    }
            }
            if (x == -1)
                    Console.WriteLine( "No negative cycle from " << v;
            else {
                    int y = x;
                    for (int i=0; i<n; ++i)
                            y = p[y];
                    List<int> path;
                    for (int cur=y; ; cur=p[cur]) {
                            path.push_back (cur);
                            if (cur == y && path.size() > 1)  break;
                    }
                    reverse (path.begin(), path.end());
                    Console.WriteLine( "Negative cycle: ";
                    for (size_t i=0; i<path.size(); ++i)
                            Console.WriteLine( path[i] << ' ';
            }
    }
    d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost);
}

C++ 解法

匹配/原始

struct edge {
        int a, b, cost;
};
int n, m, v;
vector<edge> e;
const int INF = 1000000000;
void solve() {
        vector<int> d (n, INF);
        d[v] = 0;
        for (int i=0; i<n-1; ++i)
                for (int j=0; j<m; ++j)
                        if (d[e[j].a] < INF)
                                d[e[j].b] = min (d[e[j].b], d[e[j].a] + e
[j].cost);
        // вывод d, например, на экран
}
void solve() {
        vector<int> d (n, INF);
        d[v] = 0;
        for (;;) {
                bool any = false;
                for (int j=0; j<m; ++j)
                        if (d[e[j].a] < INF)
                                if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                        d[e[j].b] = d[e[j].a] + e[j].cost;
                                        any = true;
                                }
                if (!any)  break;
        }
        // вывод d, например, на экран
}
void solve() {
        vector<int> d (n, INF);
        d[v] = 0;
        vector<int> p (n, -1);
        for (;;) {
                bool any = false;
                for (int j=0; j<m; ++j)
                        if (d[e[j].a] < INF)
                                if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                        d[e[j].b] = d[e[j].a] + e[j].cost;
                                        p[e[j].b] = e[j].a;
                                        any = true;
                                }
                if (!any)  break;
        }
        if (d[t] == INF)
                cout << "No path from " << v << " to " << t << ".";
        else {
                vector<int> path;
                for (int cur=t; cur!=-1; cur=p[cur])
                        path.push_back (cur);
                reverse (path.begin(), path.end());
                cout << "Path from " << v << " to " << t << ": ";
                for (size_t i=0; i<path.size(); ++i)
                        cout << path[i] << ' ';
        }
}
void solve() {
        vector<int> d (n, INF);
        d[v] = 0;
        vector<int> p (n, -1);
        int x;
        for (int i=0; i<n; ++i) {
                x = -1;
                for (int j=0; j<m; ++j)
                        if (d[e[j].a] < INF)
                                if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                        d[e[j].b] = max (-INF, d[e[j].a] + e
[j].cost);
                                        p[e[j].b] = e[j].a;
                                        x = e[j].b;
                                }
        }
        if (x == -1)
                cout << "No negative cycle from " << v;
        else {
                int y = x;
                for (int i=0; i<n; ++i)
                        y = p[y];
                vector<int> path;
                for (int cur=y; ; cur=p[cur]) {
                        path.push_back (cur);
                        if (cur == y && path.size() > 1)  break;
                }
                reverse (path.begin(), path.end());
                cout << "Negative cycle: ";
                for (size_t i=0; i<path.size(); ++i)
                        cout << path[i] << ' ';
        }
}
d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost);

Java 解法

自动草稿，提交前请检查

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct edge {
            int a, b, cost;
    };
    int n, m, v;
    vector<edge> e;
    const int INF = 1000000000;
    void solve() {
            ArrayList<Integer> d (n, INF);
            d[v] = 0;
            for (int i=0; i<n-1; ++i)
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    d[e[j].b] = min (d[e[j].b], d[e[j].a] + e
    [j].cost);
            // вывод d, например, на экран
    }
    void solve() {
            ArrayList<Integer> d (n, INF);
            d[v] = 0;
            for (;;) {
                    boolean any = false;
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                            d[e[j].b] = d[e[j].a] + e[j].cost;
                                            any = true;
                                    }
                    if (!any)  break;
            }
            // вывод d, например, на экран
    }
    void solve() {
            ArrayList<Integer> d (n, INF);
            d[v] = 0;
            ArrayList<Integer> p (n, -1);
            for (;;) {
                    boolean any = false;
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                            d[e[j].b] = d[e[j].a] + e[j].cost;
                                            p[e[j].b] = e[j].a;
                                            any = true;
                                    }
                    if (!any)  break;
            }
            if (d[t] == INF)
                    System.out.println( "No path from " << v << " to " << t << ".";
            else {
                    ArrayList<Integer> path;
                    for (int cur=t; cur!=-1; cur=p[cur])
                            path.push_back (cur);
                    reverse (path.begin(), path.end());
                    System.out.println( "Path from " << v << " to " << t << ": ";
                    for (size_t i=0; i<path.size(); ++i)
                            System.out.println( path[i] << ' ';
            }
    }
    void solve() {
            ArrayList<Integer> d (n, INF);
            d[v] = 0;
            ArrayList<Integer> p (n, -1);
            int x;
            for (int i=0; i<n; ++i) {
                    x = -1;
                    for (int j=0; j<m; ++j)
                            if (d[e[j].a] < INF)
                                    if (d[e[j].b] > d[e[j].a] + e[j].cost) {
                                            d[e[j].b] = max (-INF, d[e[j].a] + e
    [j].cost);
                                            p[e[j].b] = e[j].a;
                                            x = e[j].b;
                                    }
            }
            if (x == -1)
                    System.out.println( "No negative cycle from " << v;
            else {
                    int y = x;
                    for (int i=0; i<n; ++i)
                            y = p[y];
                    ArrayList<Integer> path;
                    for (int cur=y; ; cur=p[cur]) {
                            path.push_back (cur);
                            if (cur == y && path.size() > 1)  break;
                    }
                    reverse (path.begin(), path.end());
                    System.out.println( "Negative cycle: ";
                    for (size_t i=0; i<path.size(); ++i)
                            System.out.println( path[i] << ' ';
            }
    }
    d[e[j].b] = max (-INF, d[e[j].a] + e[j].cost);
}

Материал разбит как 算法ическая 题目: изучить постановку, понять асимптотику и реализовать 算法 на выбранном языке.

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。

E034. Bellman-Ford algorithm

Пусть дан ориентированный взвешенный 图

с

vertexми и

рёбрами, и указана некоторая vertex

. it is required find длины кратчайших путей от вершины

Описание 算法а

Заведём 数组 расстояний

, а все остальные elementы

равны

бесконечности

стоимости

. Релаксация вдоль ребра — это попытка улучшить значение

значением

. Фактически это значит, что

мы пытаемся улучшить ответ для вершины

, пользуясь edgeм

и текущим ответом для вершины

Утверждается, что достаточно

останется равным бесконечности

实现

в виде одного списка всех рёбер (а не

списков рёбер — рёбер из каждой вершины). В приведённой

реализации заводится структура данных

для ребра. 输入ными данными для 算法а являются числа

, список

рёбер, и номер стартовой вершины

. Все номера вершин нумеруются с

по

Простейшая 实现

Константа

struct edge {

vector<edge> e;

const int INF = 1000000000;

void solve() {

vector<int> d (n, INF);

d[v] = 0;

d[e[j].b] = min (d[e[j].b], d[e[j].a] + e

[j].cost);

// вывод d, на示例, на экран

вида

,

Улучшенная 实现

все

— он

void solve() {

vector<int> d (n, INF);

d[v] = 0;

bool any = false;

d[e[j].b] = d[e[j].a] + e[j].cost;

any = true;

// вывод d, на示例, на экран

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

Для этого заведём ещё один 数组

является кратчайшим путём до какой-то вершины

, к которому приписали в конец вершину

в момент улучшения нам надо просто запоминать в

void solve() {

vector<int> d (n, INF);

d[v] = 0;

vector<int> p (n, -1);

bool any = false;

d[e[j].b] = d[e[j].a] + e[j].cost;

p[e[j].b] = e[j].a;

any = true;

cout << "No path from " << v << " to " << t << ".";

else {

vector<int> path;

path.push_back (cur);

reverse (path.begin(), path.end());

cout << "Path from " << v << " to " << t << ": ";

cout << path[i] << ' ';

Здесь мы сначала проходимся по предкам, начиная с вершины

, и сохраняем весь пройденный путь в списке

В этом списке получается 最短路径 от

до

, но в обратном порядке, поэтому мы вызываем

от него

证明 算法а

Во-первых, сразу заметим, что для недостижимых из

证明算法а