In C++ The Bellman-Ford Algorithm In this assignment, you are asked to implement
ID: 3720843 • Letter: I
Question
In C++
The Bellman-Ford Algorithm In this assignment, you are asked to implement the Bellman-Ford Algorithm which solves the single-source shortest-paths problem. Specifically, you are given as input a directed graph G = (V, E) with weight w(u, v) on each edge (u, v) € E along with a source vertex s €V. Edges may have negative weights. Input The input has the following format. There are two integers on the first line. The first integer represents the number of vertices, IV. The second integer is the number of edges, TEL. Vertices are indexed by 0, 1,..., IV-1. Each of the following |Elines has three integers u, v, w(u, v), which represent an edge (u, v) with weight wu, v). Vertex 0 is the source vertex. Output The output falls into two possible cases Case (i): There is no negative-weight cycle reachable from s. In this case, you must output TRUE on the first line, followed by the shortest distance from s to each vertex in the graph. More precisely, you must output TRUE, (0.0), (0.1), ..., (0.VI - 1), one per line. Recall that 8(u, v) denotes the shortest distance from u to v. If a vertex v is not reachable, output INFINITY in place of 8(0, v). Case (ii): There is a negative-weight cycle reachable from 8. You must output FALSE. Examples of input and output Input 1 6 10 016 1 2 5 1 3 -4 1 48 2 1-2 302 3 2 7 3 4 9 407 5 2 5 Output 1 TRUE 11 INFINITY Input 2 6 11 0 1 6 1 2 5 1 3-4 -ON 35 -14 407 5 2 5 Output 2 FALSE Note that every line is followed by an enter key.Explanation / Answer
#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 Distance from Source ";
for (int i = 0; i < vertex_count; i++)
{
std::cout << vertices[i].id <<" " << vertices[i].distance <<" ";
}
}
int main()
{
Graph grp(5);
grp.add_edge(0, 1, 6);
grp.add_edge(1,2,5);
grp.add_edge(1,3,-4);
grp.add_edge(1,4,8);
grp.add_edge(2,1 ,-2);
grp.add_edge(3,0,2);
grp.add_edge(3,2,7);
grp.add_edge(3,4,9);
grp.add_edge(3,5,-14);
grp.add_edge(4, 0, 7);
grp.add_edge(5,2,5);
bool res = grp.bellman_ford(0);
if (res == true)
std::cout << "Graph contains no negative cycle : TRUE ";
else
std::cout << "Graph conatins negative cycle : FALSE ";
grp.distance_from_source();
}
/*
*/