Реализация алгоритма Беллмана Форда


Пожалуйста, просмотрите мой код и помочь мне улучшить его.

#include <iostream>
#include <vector>
#include <limits>
#include <map>

class Graph
{
    int vertex_count;

    enum { INF = std::numeric_limits<int>::max() };

    struct Vertex
    {
        int id;
        int distance;
        Vertex * parent;

        Vertex(int _id) : id(std::move(_id)),
                          distance(INF),
                          parent(nullptr)
                          {}
    };
    std::vector<Vertex> vertices;
    //std::pair<int, int> edge;
    std::map<std::pair<int, int>, int> edge_weight;

  public:
    Graph(int);
    void add_edge(int, int, int); //source, destination, weight
    bool bellman_ford(int); //source
    void distance_from_source();

  private:
    void initialize_single_source(int); //source
    void relax(int, int, int); //source, destination, weight
};

Graph::Graph(int v)
{
    vertex_count = v;
    for (int i = 0; i < vertex_count; i++)
    {
        vertices.push_back(Vertex(i));
    }
}

void Graph::initialize_single_source(int src)
{
    vertices[src].distance = 0;
}

void Graph::add_edge(int src, int dest, int weight)
{
    edge_weight.insert(std::make_pair( std::make_pair(src, dest), weight ));
}

void Graph::relax(int src, int dest, int weight)
{
    auto wt =  edge_weight.find(std::make_pair(src, dest));
    if (vertices[dest].distance > (vertices[src].distance + wt->second))
    {
        vertices[dest].distance = (vertices[src].distance + wt->second);
        vertices[dest].parent = &vertices[src];
    }
}

bool Graph::bellman_ford(int src)
{
    initialize_single_source(src);
    for (int i = 0; i < vertex_count - 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;
}

void Graph::distance_from_source()
{
    std::cout << "Vertex\t\tDistance from Source\n";
    for (int i = 0; i < vertex_count; i++)
    {
        std::cout << 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();
}


2089
4
задан 6 марта 2018 в 10:03 Источник Поделиться
Комментарии
2 ответа

Класс вершинного

В INF константа используется только в качестве инициализатора Vertex::distanceпоэтому я бы рядный значение напрямую, как это:

struct Vertex
{
const int id;
int distance = std::numeric_limits<int>::max();
Vertex *parent = nullptr;

Vertex(int id)
: id(id)
{}
};

Я кликабельны инициализаторов, которые не зависят от аргументов, и я удалил std::move оттенок, который не имеет никакой пользы для примитивного типа. Так что конструктор сейчас же, как по умолчанию, мы можем его опустить.

Графа класс

В vertex_count участник может (и должен) быть признан const; это также требует, чтобы он был инициализирован (не назначен) в конструкторе. Тем не менее, нет никакой необходимости в этом, как мы можем всегда использовать vertices.size().

Аргумент конструктора не очевидно из определения класса - имя его и при необходимости добавьте комментарий.

Именование: distance_from_source() похоже, он может быть использован для получения результатов, но это на самом деле печатает в стандартный вывод. Я бы переименовать его в что-то подобное (с использованием #include <iosfwd>):

std::ostream& print_distances(std::ostream&) const;

Конструктор

Мы должны сказать, вектор его конечный размер, поэтому он может резервные возможности и избежать нескольких распределений.

Мы можем использовать emplace_back() для упрощения населения вектора:

Graph::Graph(int v)
: vertex_count(v)
{
vertices.reserve(vertex_count);
for (int i = 0; i < vertex_count; ++i) {
vertices.emplace_back(i);
}
}

Добавление краев

В add_edge метод не проверить, что src и dest находятся в пределах диапазона, и это не делает ничего, если край уже существует. Мы можем легко обнаружить эти условия:

void Graph::add_edge(int src, int dest, int weight)
{
if (src == dest) {
throw std::logic_error("src==dest");
}
if (src < 0 || vertex_count <= src) {
throw std::out_of_range("src");
}
if (dest < 0 || vertex_count <= dest) {
throw std::out_of_range("dest");
}

auto const inserted = edge_weight.insert({ {src, dest}, weight });
if (!inserted.second) {
throw std::logic_error("existing edge");
}
}

Я рекомендую изменение индекс тип из int для беззнакового типа (например, std::size_t) как отрицательные значения не допустимы.

Кроме того, использование std::pair а не особая структура делает его трудно следовать кодексу, полный first и second смысл разные вещи.

Расслабляющий Весов

Это неэффективно повторноfind() край. Тем не менее, мы проходим weight чтобы избежать этого, поэтому просто повторно использовать его:

void Graph::relax(int src, int dest, int weight)
{
auto & existing = vertices[dest].distance;
auto const proposed = vertices[src].distance + weight;
if (proposed < existing) {
existing = proposed;
}
}

Я за обновление parent поскольку мы никогда не использовать его.

Беллмана-Форда вычисления

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


Модифицированная программа

#include <iosfwd>
#include <vector>
#include <map>

class Graph
{
using index_type = std::size_t;
using distance_type = int;

static const distance_type max_distance;

struct Vertex
{
const index_type id;
distance_type distance = max_distance;
};

struct Edge
{
index_type from;
index_type to;
bool operator<(const Edge& other) const
{
return std::tie(from, to) < std::tie(other.from, other.to);
}
};

std::vector<Vertex> vertices = {};
std::map<Edge,distance_type> edge_weight = {};

public:
Graph(index_type size);
void add_edge(index_type from, index_type to, distance_type weight);
bool bellman_ford(index_type origin); // true if no negative cycles
std::ostream& print_distances(std::ostream&) const;

private:
void relax(index_type from, index_type to, distance_type weight);
};

// Implementation

#include <limits>
#include <ostream>

const Graph::distance_type Graph::max_distance
= std::numeric_limits<distance_type>::max();

Graph::Graph(index_type size)
{
vertices.reserve(size);
for (index_type i = 0; i < size; ++i) {
vertices.push_back(Vertex{i});
}
}

void Graph::add_edge(index_type src, index_type dest, distance_type weight)
{
if (src == dest) {
throw std::logic_error("src==dest");
}
if (vertices.size() <= src) {
throw std::out_of_range("src");
}
if (vertices.size() <= dest) {
throw std::out_of_range("dest");
}

auto const inserted = edge_weight.insert({ Edge{src, dest}, weight });
if (!inserted.second) {
throw std::logic_error("existing edge");
}
}

void Graph::relax(index_type src, index_type dest, distance_type weight)
{
auto& existing = vertices[dest].distance;
auto const proposed = vertices[src].distance + weight;
if (proposed < existing) {
existing = proposed;
}
}

bool Graph::bellman_ford(index_type src)
{
// initialise distances
for (auto& vertex: vertices) {
vertex.distance = max_distance;
}
vertices[src].distance = 0;

// relax edges
for (index_type i = 1; i < vertices.size(); ++i) {
for (auto edge: edge_weight) {
relax(edge.first.from, edge.first.to, edge.second);
}
}

// check for negative-weight cycles
for (auto edge: edge_weight) {
auto const& from_vertex = vertices[edge.first.from];
auto const& to_vertex = vertices[edge.first.to];
if (to_vertex.distance > from_vertex.distance + edge.second) {
return false;
}
}

// success!
return true;
}

std::ostream& Graph::print_distances(std::ostream& os) const
{
os << "Vertex\t\tDistance from Source\n";
for (auto vertex: vertices) {
os << vertex.id << "\t\t" << vertex.distance << "\n";
}
return os;
}

// Test program

#include <iostream>

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);

if (grp.bellman_ford(0))
std::cout << "Graph contains no negative cycle \n";
else
std::cout << "Graph conatins negative cycle \n";

grp.print_distances(std::cout);
}

6
ответ дан 6 марта 2018 в 01:03 Источник Поделиться

Не используя using namespace std вы уже на опережение, молодцы.


  • Почему часть вашего класса вне вашей частной/общественной сферы? В этом случае он будет по умолчанию, так что вы должны переместить его, чтобы избежать путаницы.

  • Использование предупреждений компилятора. У вас есть неиспользуемый параметр (вес) в ваш отдых функция. Включение -Weffc++ появится еще одна действительная точка. Вы используете инициализатор элемента список для вершины структуры, поэтому почему бы не использовать его для графа класс, а?

  • Почему ты опуская имена параметров, а затем добавить их в комментариях? Просто добавить названия параметра интерфейс класса и получить взамен от комментариев.

  • Почему у вас одна линия функция (initialize_single_source), который вызывается только один раз?

  • Я не знаю, какой компилятор/стандартный вы используете, но если возможно, вы должны рассмотреть возможность использования некоторых новых возможностей (ограниченных перечислений, смарт-указатели, диапазон, основанный на петли).

5
ответ дан 6 марта 2018 в 10:03 Источник Поделиться