Implementation of Bellman Ford's Algorithm

To understand the implementation of Bellman Ford's Algorithm using C++

Objective

To understand the implementation of Bellman Ford's Algorithm using C++

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    struct Edge* edge;
};

struct Graph* createGraph(int V, int E) {
    struct Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[E];
    return graph;
}

void printArr(int dist[], int n) {
    cout << "\nVertex |  Distance from Source\n";
    for (int i = 0; i < n; ++i)
        cout<< i <<" \t | \t\t "<< dist[i]<< "\n";
}

void BellmanFord(struct Graph* graph, int src) {
    int V = graph->V;
    int E = graph->E;
    int dist[V];

    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    for (int i = 1; i <= V-1; i++) {
        for (int j = 0; j < E; j++) {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    for (int i = 0; i < E; i++) {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            cout<<"Graph contains negative weight cycle";
            return;
        }
    }

    printArr(dist, V);

    return;
}

int main() {
    int V, E;
    cout << "Enter number of vertices: ";
    cin>>V;
    cout<< "Enter number of edges: ";
    cin>>E;

    struct Graph* graph = createGraph(V, E);

    for(int i=0; i < E; i++) {
        cout << "Enter source vertex, destination vertex and weight for edge "<< i+1<<": ";
        cin>>graph->edge[i].src>>graph->edge[i].dest>>graph->edge[i].weight;
    }

    BellmanFord(graph, 0);

    return 0;
}

Discussion of Algorithm

1. Start
2. Set the distance of the source vertex to 0 and all other vertices to infinity.
3. For each vertex, apply relaxation for all the edges.
4. Repeat step 3 for V-1 times.
5. Perform step 3 one more time and if any distance is updated then the graph has a negative cycle.
6. End

Representations

Flow Diagram

   +----------------------------------+
   |                                  |
   |            Start                 |
   |            |                     |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |           int V, E;              |
   |              |                   |
   +----------------------------------+
   
                  |
                  V
   +----------------------------------+
   |                                  |
   |    Create the graph structure    |
   |       and input the data         |
   |                                  |
   |       struct Graph* graph =      |
   |        createGraph(V, E);        |
   |     cin>>graph->edge[i].src>>    |
   |       graph->edge[i].dest>>      |
   |       graph->edge[i].weight;     |
   |                                  |
   +----------------------------------+
   
                  |
                  V
   +----------------------------------+
   |                                  |
   |    Bellman-Ford Algorithm        |
   |    (Single Source Shortest Path) |
   |                                  |
   |           int dist[V];           |
   |          dist[src] = 0;          |
   |    Perform relaxation steps      |
   |    Check for negative weight     |
   |    cycles                        |
   |                                  |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |    Print the distances           |
   |    from the source vertex        |
   |                                  |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |             Exit                 |
   |              |                   |
   +----------------------------------+

Tabular Dry Run

Output

Enter number of vertices: 5
Enter number of edges: 8
Enter source vertex, destination vertex and weight for edge 1: 0 1 -1
Enter source vertex, destination vertex and weight for edge 2: 0 2 4
Enter source vertex, destination vertex and weight for edge 3: 1 2 3
Enter source vertex, destination vertex and weight for edge 4: 1 3 2
Enter source vertex, destination vertex and weight for edge 5: 1 4 2
Enter source vertex, destination vertex and weight for edge 6: 3 2 5
Enter source vertex, destination vertex and weight for edge 7: 3 1 1
Enter source vertex, destination vertex and weight for edge 8: 4 3 -3

Vertex | Distance from Source
0      |         0
1      |         -1
2      |         2
3      |         -2
4      |         1