Bellman-Ford Algorithm

Algorithm Description

The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph with negative edge weights. It iterates over all edges multiple times, relaxing them by attempting to update the shortest path distances until convergence, ensuring an efficient O(V * E) time complexity in typical cases.

C++ Code

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

#define INF numeric_limits<int>::max()
#define V 6 
#define E 7 

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

void bellmanFord(vector<Edge>& edges, int source) {
    vector<int> dist(V, INF);
    dist[source] = 0;

    for (int i = 1; i <= V - 1; ++i) {
        for (const auto& edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;

            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    for (const auto& edge : edges) {
        int u = edge.src;
        int v = edge.dest;
        int weight = edge.weight;

        if (dist[u] != INF && dist[u] + weight < dist[v]) {
            cout << "Graph contains negative weight cycle\n";
            return;
        }
    }

    cout << "Shortest distances from source vertex " << source << ":\n";
    for (int i = 0; i < V; ++i) {
        cout << "Vertex " << i << ": " << dist[i] << "\n";
    }
}

int main() {
    vector<Edge> edges = {
        {0, 1, 4}, {0, 2, 1}, {1, 3, 1}, {2, 1, 2},
        {2, 3, 5}, {3, 4, 3}, {4, 5, 2}
    };

    int source = 0;
    bellmanFord(edges, source);

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Initialization	O(V)	O(V + E)
Bellman-Ford Algorithm	O(V * E)	O(V)

Where:

• V: Number of vertices in the graph.
• E: Number of edges in the graph.

← Back to Homepage