Vertex class
The INF constant is used only as the initializer for Vertex::distance, so I'd inline the value directly, like this:
struct Vertex
{
const int id;
int distance = std::numeric_limits<int>::max();
Vertex *parent = nullptr;
Vertex(int id)
: id(id)
{}
};
I've inlined the initializers that don't depend on arguments, and I've removed the std::move cast that has no benefit for a primitive type. Since that constructor is now the same as default, we can omit it.
Graph class
The vertex_count member can (and should) be declared const; that also requires it to be initialized (not assigned) in the constructor. That said, there's no need for it, as we can always use vertices.size().
The constructor argument isn't obvious from the class definition - name it and if necessary also add a comment.
Naming: distance_from_source() sounds like it can be used to obtain the results, but it actually prints to standard output. I'd rename it to something like (using #include <iosfwd>):
std::ostream& print_distances(std::ostream&) const;
Constructor
We should tell the vector its final size, so it can reserve capacity and avoid multiple allocations.
We can use emplace_back() to simplify the population of the vector:
Graph::Graph(int v)
: vertex_count(v)
{
vertices.reserve(vertex_count);
for (int i = 0; i < vertex_count; ++i) {
vertices.emplace_back(i);
}
}
Adding edges
The add_edge method doesn't check that src and dest are within range, and it does nothing if an edge already exists. We can easily detect these conditions:
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");
}
}
I recommend changing the index type from int to an unsigned type (e.g. std::size_t) as negative values are not valid.
Also, the use of std::pair rather than a specific structure makes it hard to follow code full of first and second all meaning different things.
Relaxing weights
It's inefficient to have to re-find() an edge. However, we're passing weight to avoid that, so just re-use it:
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;
}
}
I've dropped the update to parent since we never use it.
Bellman-Ford computation
If we want to recalculate with a different origin node, we'll need to reset initial distances to maximum, as well as setting the origin to zero.
Modified program
#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);
}
