I have written this code for bellman-ford algorithm. Please review and suggest improvements:
This code takes input graph as an adjacency matrix, and stores it the same way with additional info as
a graph object. It then finds the shortest path to all vertices from the vertex at location [0][0] in
the adjacency matrix. I still haven't been able to figure out an efficient way to detect negative
weight cycle and am open for suggestions.
struct Node {
long id;
Node() { }
explicit Node(long node_id) : id(node_id) { }
bool operator==(const Node& node) {
return this->id == node.id;
}
};
class Graph {
struct Edge {
Node start;
Node end;
long length;
explicit Edge(Node n1, Node n2, long len = 0) : start(n1), end(n2), length(len) { }
bool operator==(const Edge& node) {
return ((this->start.id == node.start.id) && (this->end.id == node.end.id));
}
};
std::vector<std::vector<int>> matrix;
std::list<Node> node_list;
std::list<Edge> edge_list;
unsigned long count;
void createGraph() {
std::cout << "Enter the number of Nodes: ";
std::cin >> count;
for (int i = 0; i < count; i++) {
std::vector<int> v;
node_list.push_back(Node(i + 1));
for (int j = 0; j < count; j++) {
long temp;
std::cin >> temp;
v.push_back(temp);
}
matrix.push_back(v);
}
}
void createGraph(const int** adj_matrix) {
for (unsigned long long i = 0; i < *(&adj_matrix + 1) - adj_matrix; i++) {
std::vector<int> vec;
node_list.push_back(Node(i + 1));
for (unsigned long long j = 0; j < *(&adj_matrix + 1) - adj_matrix; j++) {
int temp = 0;
std::cin >> temp;
vec.push_back(temp);
}
matrix.push_back(vec);
}
}
void createGraph(const std::vector<std::vector<int>>& graph) {
int i = 0;
for (const auto& node : graph) {
node_list.push_back(Node(i + 1));
i++;
std::vector<int> vec;
for (const auto& neighbour : node) {
vec.push_back(neighbour);
}
matrix.push_back(vec);
}
}
void addEdges() {
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[i].size(); j++) {
if (matrix[i][j]) {
Node start(i + 1);
Node end(j + 1);
edge_list.push_back(Edge(start, end, matrix[i][j]));
}
}
}
}
public:
Graph() {
createGraph();
addEdges();
}
explicit Graph(const int** adj_mat) {
createGraph(adj_mat);
count = matrix.size();
addEdges();
}
explicit Graph(const std::vector<std::vector<int>>& graph) {
createGraph(graph);
count = matrix.size();
addEdges();
}
inline std::list<Node> getNodes() {
return node_list;
}
long edgeLength(const Node& node1, const Node& node2) {
for (const auto& edge : edge_list) {
if (edge.start.id == node1.id && edge.end.id == node2.id) {
return edge.length;
}
}
return 0;
}
bool edgeExists(const Node& node1, const Node& node2) {
if (std::find(edge_list.begin(), edge_list.end(), Edge(node1, node2)) == edge_list.end()) {
return false;
}
return true;
}
void printGraph() {
for (const auto& row : matrix) {
for (const auto& elem : row) {
std::cout << elem << " ";
}
std::cout << "\n";
}
}
};
std::vector<std::pair<Node, long>> bellman_ford(Graph gr) {
std::list<Node> v_list = gr.getNodes();
std::vector<long> node_distance(v_list.size());
std::fill(node_distance.begin() + 1, node_distance.end(), std::numeric_limits<long>::max());
for (int i = 0; i < v_list.size() - 1; i++) {
for (auto& u : v_list) {
for (auto& v : v_list) {
if (gr.edgeExists(u, v)) {
if (node_distance[v.id - 1] == std::numeric_limits<long>::max()) {
node_distance[v.id - 1] = node_distance[u.id - 1] + gr.edgeLength(u, v);
}
else if (node_distance[v.id - 1] > node_distance[u.id - 1] + gr.edgeLength(u, v)) {
node_distance[v.id - 1] = node_distance[u.id - 1] + gr.edgeLength(u, v);
}
}
}
}
}
std::vector<std::pair<Node, long>> shortest_distance(v_list.size());
auto list_it = v_list.begin();
auto dist_it = node_distance.begin();
for (auto& pair : shortest_distance) {
pair.first.id = list_it->id;
pair.second = *dist_it;
std::advance(list_it, 1);
std::advance(dist_it, 1);
}
return shortest_distance;
}
