Bellman Ford algorithm implementation Please review my code and help me to improve it.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;limits&gt;
#include &lt;map&gt;

class Graph
{
    int vertex_count;

    enum { INF = std::numeric_limits&lt;int&gt;::max() };

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

        Vertex(int _id) : id(std::move(_id)),
                          distance(INF),
                          parent(nullptr)
                          {}
    };
    std::vector&lt;Vertex&gt; vertices;
    //std::pair&lt;int, int&gt; edge;
    std::map&lt;std::pair&lt;int, int&gt;, int&gt; 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 &lt; 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 &gt; (vertices[src].distance + wt-&gt;second))
    {
        vertices[dest].distance = (vertices[src].distance + wt-&gt;second);
        vertices[dest].parent = &amp;vertices[src];
    }
}

bool Graph::bellman_ford(int src)
{
    initialize_single_source(src);
    for (int i = 0; i &lt; vertex_count - 1; i++)
    {
        for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
        {
            relax(it-&gt;first.first, it-&gt;first.second, it-&gt;second);
        }
    }

    for (auto it = edge_weight.begin(); it != edge_weight.end(); it++)
    {
        if (vertices[it-&gt;first.second].distance &gt; (vertices[it-&gt;first.first].distance + it-&gt;second))
           return false;
    }
    return true;
}

void Graph::distance_from_source()
{
    std::cout &lt;&lt; "Vertex\t\tDistance from Source\n";
    for (int i = 0; i &lt; vertex_count; i++)
    {
        std::cout &lt;&lt; vertices[i].id &lt;&lt;"\t\t" &lt;&lt; vertices[i].distance &lt;&lt;"\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 &lt;&lt; "Graph contains no negative cycle \n";
    else
       std::cout &lt;&lt; "Graph conatins negative cycle \n";

    grp.distance_from_source();
}
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&lt;int&gt;::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 &lt;iosfwd&gt;):

std::ostream&amp; print_distances(std::ostream&amp;) 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 &lt; 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 &lt; 0 || vertex_count &lt;= src) {
        throw std::out_of_range("src");
    }
    if (dest &lt; 0 || vertex_count &lt;= 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 &amp; existing = vertices[dest].distance;
    auto const proposed = vertices[src].distance + weight;
    if (proposed &lt; 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 &lt;iosfwd&gt;
#include &lt;vector&gt;
#include &lt;map&gt;

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&lt;(const Edge&amp; other) const
        {
            return std::tie(from, to) &lt; std::tie(other.from, other.to);
        }
    };

    std::vector&lt;Vertex&gt; vertices = {};
    std::map&lt;Edge,distance_type&gt; 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&amp; print_distances(std::ostream&amp;) const;

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




// Implementation

#include &lt;limits&gt;
#include &lt;ostream&gt;

const Graph::distance_type Graph::max_distance
    = std::numeric_limits&lt;distance_type&gt;::max();

Graph::Graph(index_type size)
{
    vertices.reserve(size);
    for (index_type i = 0;  i &lt; 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() &lt;= src) {
        throw std::out_of_range("src");
    }
    if (vertices.size() &lt;= 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&amp; existing = vertices[dest].distance;
    auto const proposed = vertices[src].distance + weight;
    if (proposed &lt; existing) {
        existing = proposed;
    }
}

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

    // relax edges
    for (index_type i = 1;  i &lt; 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&amp; from_vertex = vertices[edge.first.from];
        auto const&amp; to_vertex = vertices[edge.first.to];
        if (to_vertex.distance &gt; from_vertex.distance + edge.second) {
            return false;
        }
    }

    // success!
    return true;
}

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




// Test program

#include &lt;iostream&gt;

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 &lt;&lt; "Graph contains no negative cycle \n";
    else
        std::cout &lt;&lt; "Graph conatins negative cycle \n";

    grp.print_distances(std::cout);
}