Practicals
Semester-05
DAAL
Assignment 02

Assignment-02

Title

Implementing the Bellman-Ford Algorithm Using Dynamic Programming

Theory

The Bellman-Ford algorithm is used to find the shortest path from a single source to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative weights and can detect negative weight cycles. The algorithm is based on dynamic programming and follows these steps:

  1. Initialization: Set the distance to the source vertex to 0 and all other vertices to infinity.
  2. Relaxation: For each edge, update the distance to the destination vertex if a shorter path is found. This step is repeated for all vertices minus one.
  3. Negative Cycle Detection: Check for negative weight cycles by verifying if further relaxation is possible. If any distance is updated, a negative weight cycle exists.

The time complexity of the Bellman-Ford algorithm is (O(V \cdot E)), where (V) is the number of vertices and (E) is the number of edges.

Code Implementation

#include <bits/stdc++.h>
using namespace std;
 
void bellmanFord(int v, int e, vector<vector<int>> &graph) {
    vector<int> dist(v, INT_MAX);
    dist[0] = 0;
 
    // Relax all edges |V| - 1 times.
    for (int i = 0; i < v - 1; i++) {
        for (auto edge : graph) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
 
    // Check for negative-weight cycles.
    for (auto edge : graph) {
        int u = edge[0];
        int v = edge[1];
        int w = edge[2];
        if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
            cout << "Negative cycle detected" << endl;
            return;
        }
    }
 
    for (int i = 0; i < v; i++) {
        cout << "Distance of vertex " << i << " from source is " << dist[i] << endl;
    }
}
 
int main() {
    int v, e;
    cout << "Enter the number of vertices and edges: ";
    cin >> v >> e;
 
    vector<vector<int>> graph;
 
    for (int i = 0; i < e; i++) {
        int u, v, w;
        cout << "Enter the source, destination and weight of edge " << i + 1 << ": ";
        cin >> u >> v >> w;
        graph.push_back({u, v, w});
    }
 
    auto start = chrono::high_resolution_clock::now();
    bellmanFord(v, e, graph);
    auto end = chrono::high_resolution_clock::now();
 
    chrono::duration<double> duration = end - start;
    cout << "Time taken by Bellman-Ford algorithm: " << duration.count() << " seconds" << endl;
 
    return 0;
}

Setup and Run

Step 1: Save the Code

Save the code as bellman_ford.cpp.

Step 2: Compile the Code

Open a terminal and navigate to the directory where the file is saved. Compile the program using the GCC compiler:

g++ -o bellman_ford bellman_ford.cpp -std=c++11

Step 3: Run the Program

Run the compiled program:

./bellman_ford

Example

Input:

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

Output:

Distance of vertex 0 from source is 0
Distance of vertex 1 from source is -1
Distance of vertex 2 from source is 2
Distance of vertex 3 from source is -2
Distance of vertex 4 from source is 1
Time taken by Bellman-Ford algorithm: X seconds

Explanation

  1. Initialization:

    • The distance to the source vertex (vertex 0) is set to 0.
    • The distances to all other vertices are set to infinity.

  2. Relaxation:

    • For each edge, the algorithm updates the distance to the destination vertex if a shorter path is found.
    • This step is repeated for (V-1) times (where (V) is the number of vertices).

  3. Negative Cycle Detection:

    • The algorithm checks for negative weight cycles by verifying if further relaxation is possible. If any distance is updated in this step, it indicates the presence of a negative weight cycle.

By running this program, you will observe how the Bellman-Ford algorithm efficiently finds the shortest paths in a weighted graph, handles negative weights, and detects negative weight cycles. The output also includes the time taken to execute the algorithm, demonstrating its time complexity.

Contact

For any questions or clarifications, please contact Parth Sali at parthsali04@gmail.com.

Assignment 01Assignment 03