Алгоритм Беллмана-Форда находит кратчайший путь от исходной вершины ко всем вершинам графа. Граф может содержать ребра с отрицательным весом, но не должен содержать цикл с отрицательным весом, достижимый из исходной вершины.
Алгоритм возвращает TRUE, если нет цикла с отрицательным весом, и FALSE, если существует цикл с отрицательным весом, достижимый из исходной вершины. Если существует цикл с отрицательным весом, достижимый из исходной вершины, то решения не существует.
На рис. (a) цикл с отрицательным весом отсутствует, поэтому алгоритм Беллмана Форда находит кратчайший путь от источника, если рис. (а) находится на графике, тогда как рис. (b) содержит цикл с отрицательным весом, поэтому решения не существует.
На рис. а) граф находится в исходной конфигурации. Все вершины находились на бесконечном расстоянии от исходной вершины a. Затем достигаются вершины b и c и обновляется их расстояние от вершины a.
На рис. (d) сумма расстояний пути a -> b -> d равна 2 + 5 = 7, тогда как сумма расстояний пути a -> c -> d равна 7 + (-3) = 4. Следовательно, предпочтительным является путь a -> c -> d, показанный красной линией. На рис. (e) красная линия показывает кратчайший путь от a до e.
Структура данных необходима для хранения расстояния вершины от исходной вершины.
Вот реализация функций bellman_ford
и relax
.
struct Vertex
{
std::size_t id;
int distance = std::numeric_limits<int>::max();
Vertex(std::size_t id) : id(id) {}
};
void relax(std::size_t src, std::size_t dest, int weight)
{
if (vertices[dest].distance > (vertices[src].distance + weight))
{
vertices[dest].distance = (vertices[src].distance + weight);
}
}
bool bellman_ford(std::size_t src)
{
//initialize distance of source
vertices[src].distance = 0;
for (int i = 0; i < vertices.size() - 1; i++)
{
for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
{
relax(it->first.first, it->first.second, it->second);
}
}
for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
{
if (vertices[it->first.second].distance
> (vertices[it->first.first].distance + it->second))
return false;
}
return true;
}
Функция relax
обновляет расстояние вершины от исходной вершины, если новое рассчитанное расстояние меньше сохраненного расстояния.
Временная сложность алгоритма Беллмана Форда составляет O(nm), где n — количество вершин, а m — количество ребер.
По теме: Алгоритм Дейкстры
Вот реализация С++ алгоритма Беллмана-Форда
#include <iostream>
#include <vector>
#include <limits>
#include <map>
class Graph
{
struct Vertex
{
std::size_t id;
int distance = std::numeric_limits<int>::max();
Vertex(std::size_t id) : id(id) {}
};
std::vector<Vertex> vertices;
std::map<std::pair<std::size_t, std::size_t>, int> edge_weight;
public:
Graph(std::size_t);
void add_edge(std::size_t, std::size_t, int); //source, destination, weight
bool bellman_ford(std::size_t); //source
std::ostream& distance_from_source(std::ostream&) const;
private:
void relax(std::size_t, std::size_t, int); //source, destination, weight
};
Graph::Graph(std::size_t size)
{
vertices.reserve(size);
for (int i = 0; i < size; i++)
{
vertices.push_back(Vertex(i));
}
}
void Graph::add_edge(std::size_t src, std::size_t dest, int weight)
{
if (src == dest)
throw std::logic_error("Source and destination vertices are same");
if (src < 0 || vertices.size() <= src)
throw std::out_of_range("Enter correct source vertex");
if (dest < 0 || vertices.size() <= dest)
throw std::out_of_range("Enter correct destination vertex");
const auto inserted = edge_weight.insert(std::make_pair(
std::make_pair(src, dest), weight ));
if (!inserted.second)
throw std::logic_error("Existing edge");
}
void Graph::relax(std::size_t src, std::size_t dest, int weight)
{
if (vertices[dest].distance > (vertices[src].distance + weight))
{
vertices[dest].distance = (vertices[src].distance + weight);
}
}
bool Graph::bellman_ford(std::size_t src)
{
//initialize distance of source
vertices[src].distance = 0;
for (int i = 0; i < vertices.size() - 1; i++)
{
for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
{
relax(it->first.first, it->first.second, it->second);
}
}
for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
{
if (vertices[it->first.second].distance
> (vertices[it->first.first].distance + it->second))
return false;
}
return true;
}
std::ostream& Graph::distance_from_source(std::ostream& os) const
{
os << "Vertex\t\tDistance from Source\n";
for (int i = 0; i < vertices.size(); i++)
{
os << vertices[i].id <<"\t\t" << vertices[i].distance <<"\n";
}
}
int main()
{
Graph grp(5);
grp.add_edge(0, 1, 6);
grp.add_edge(0, 2, 7);
grp.add_edge(1, 3, 5);
grp.add_edge(1, 4, -4);
grp.add_edge(1, 2, 8);
grp.add_edge(2, 3, -3);
grp.add_edge(2, 4, 9);
grp.add_edge(3, 1, -2);
grp.add_edge(4, 0, 2);
grp.add_edge(4, 3, 7);
bool res = grp.bellman_ford(0);
if (res == true)
std::cout << "Graph contains no negative cycle \n";
else
std::cout << "Graph conatins negative cycle \n";
grp.distance_from_source(std::cout);
}
Вывод
Ссылка:
Введение в алгоритмы
Руководство по проектированию алгоритмов
Простые структуры данных и алгоритмы
Справочник конкурентоспособного программиста — Антти Лааксонен
Вам также может понравиться
Поиск в ширину с использованием списка смежности | Обход графа
Поиск в глубину с использованием списка смежности | Обход графа
Следите за мной в Facebook и Twitter
Первоначально опубликовано на https://programmercave0.github.io 11 марта 2018 г.