bellmanalg.cpp

#include <iostream>
using namespace std;

class BellmanFord {
    int **edges, *dist, *parent, vertices, edgesCount;

public:
    BellmanFord(int v, int e) {
        vertices = v;
        edgesCount = e;
        edges = new int*[edgesCount];
        for (int i = 0; i < edgesCount; i++)
            edges[i] = new int[3];
        
        dist = new int[vertices];
        parent = new int[vertices];
    }

    void inputEdges() {
        cout << "Enter edges in the format (u v w) where u and v are vertices and w is weight:\n";
        for (int i = 0; i < edgesCount; i++) {
            cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
        }
    }

    void bellmanFord(int src) {
        for (int i = 0; i < vertices; i++) {
            dist[i] = 9999;
            parent[i] = -1;
        }
        dist[src] = 0;

        for (int i = 0; i < vertices - 1; i++) {
            for (int j = 0; j < edgesCount; j++) {
                int u = edges[j][0];
                int v = edges[j][1];
                int w = edges[j][2];
                if (dist[u] != 9999 && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    parent[v] = u;
                }
            }
        }

        for (int j = 0; j < edgesCount; j++) {
            int u = edges[j][0];
            int v = edges[j][1];
            int w = edges[j][2];
            if (dist[u] != 9999 && dist[u] + w < dist[v]) {
                cout << "Graph contains a negative weight cycle!\n";
                return;
            }
        }
    }

    void printPath(int j) {
        if (parent[j] == -1)
            return;
        printPath(parent[j]);
        cout << " -> " << j;
    }

    void displayDistances() {
        cout << "Vertex \t Distance \t Path" << endl;
        for (int i = 0; i < vertices; i++) {
            cout << i << "\t" << dist[i] << "\t";
            cout << "" << i;
            printPath(i);
            cout << "\n";
        }
    }

    ~BellmanFord() {
        for (int i = 0; i < edgesCount; i++)
            delete[] edges[i];
        delete[] edges;
        delete[] dist;
        delete[] parent;
    }
};

int main() {
    int v, e, src;
    cout << "Enter number of vertices and edges: ";
    cin >> v >> e;
    
    BellmanFord bf(v, e);
    bf.inputEdges();
    
    cout << "Enter source vertex: ";
    cin >> src;
    
    bf.bellmanFord(src);
    bf.displayDistances();
    
    return 0;
}


/*This is the Bellman-Ford algorithm implementation in C++. It:

Accepts user input for the number of vertices and edges.

Uses dynamic memory allocation for storing edges and distances.

Detects negative weight cycles in the graph.

Displays shortest distances and paths from the source.


Let me know if you need modifications!*/