Algorithm

Bellman-Ford's algorithm is a single-source shortest path algorithm that can handle graphs with negative edge weights. It was proposed by Richard Bellman and Lester Ford, Jr. It works for both directed and undirected graphs and is particularly useful when there are negative weight edges.

Here's a high-level overview of how the Bellman-Ford algorithm works:

  1. Initialization: Initialize the distance from the source vertex to all other vertices as infinity, except the distance to the source itself, which is set to 0.

  2. Relaxation: Iterate through all edges of the graph repeatedly. In each iteration, attempt to improve the distance values by relaxing the edges. For each edge (u, v) with weight w, if the distance to the destination vertex v can be shortened by taking the edge (u, v), update the distance to v as the sum of the distance to u and the weight w.

  3. Detection of Negative Cycles: After performing the relaxation step for all edges for V-1 iterations (where V is the number of vertices), if further relaxation is possible, then there is a negative weight cycle in the graph. The algorithm can be used to detect negative cycles by running an additional iteration. If any distance can be further improved, then a negative cycle exists.

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

It's important to note that while Bellman-Ford is a versatile algorithm that can handle graphs with negative edges, it may not work correctly if there is a negative cycle reachable from the source vertex. In such cases, the algorithm may not converge to the correct shortest paths because it will keep reducing the distances indefinitely due to the negative cycle.

 

Code Examples

#1 Bellman Ford's Algorithm implement in Python

Code - Python Programming

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        # Initialize distance from source to all other vertices as infinity
        dist = [float("inf")] * self.V
        dist[src] = 0

        # Relax all edges |V| - 1 times
        for _ in range(self.V - 1):
            # Update dist value and parent index of the adjacent vertices of the picked vertex.
            for u, v, w in self.graph:
                if dist[u] != float("inf") and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        # Check for negative-weight cycles
        for u, v, w in self.graph:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return

        self.print_solution(dist)

    def print_solution(self, dist):
        print("Vertex Distance from Source")
        for i in range(self.V):
            print(f"{i}\t\t{dist[i]}")


# Example Usage
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)

g.bellman_ford(0)
Copy The Code & Try With Live Editor

#2 Bellman Ford's Algorithm implement in Java

Code - Java Programming

import java.util.Arrays;

class BellmanFord {

    static class Edge {
        int source, destination, weight;

        Edge() {
            source = destination = weight = 0;
        }
    }

    int V, E;
    Edge edge[];

    BellmanFord(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[e];
        for (int i = 0; i  <  e; ++i)
            edge[i] = new Edge();
    }

    void BellmanFordAlgorithm(BellmanFord graph, int source) {
        int V = graph.V, E = graph.E;
        int dist[] = new int[V];

        // Step 1: Initialize distances from the source to all other vertices as INFINITE
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // Step 2: Relax all edges |V| - 1 times
        for (int i = 1; i  <  V; ++i) {
            for (int j = 0; j  <  E; ++j) {
                int u = graph.edge[j].source;
                int v = graph.edge[j].destination;
                int weight = graph.edge[j].weight;
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight  <  dist[v])
                    dist[v] = dist[u] + weight;
            }
        }

        // Step 3: Check for negative-weight cycles
        for (int j = 0; j  <  E; ++j) {
            int u = graph.edge[j].source;
            int v = graph.edge[j].destination;
            int weight = graph.edge[j].weight;
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight  <  dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }

        // Print the calculated distances
        printSolution(dist, source);
    }

    void printSolution(int dist[], int source) {
        System.out.println("Vertex \t Distance from Source");
        for (int i = 0; i  <  V; ++i)
            System.out.println(i + "\t\t" + dist[i]);
    }

    public static void main(String[] args) {
        int V = 5; // Number of vertices in the graph
        int E = 8; // Number of edges in the graph

        BellmanFord graph = new BellmanFord(V, E);

        // Example graph edges with weights
        graph.edge[0].source = 0;
        graph.edge[0].destination = 1;
        graph.edge[0].weight = -1;

        graph.edge[1].source = 0;
        graph.edge[1].destination = 2;
        graph.edge[1].weight = 4;

        graph.edge[2].source = 1;
        graph.edge[2].destination = 2;
        graph.edge[2].weight = 3;

        graph.edge[3].source = 1;
        graph.edge[3].destination = 3;
        graph.edge[3].weight = 2;

        graph.edge[4].source = 1;
        graph.edge[4].destination = 4;
        graph.edge[4].weight = 2;

        graph.edge[5].source = 3;
        graph.edge[5].destination = 2;
        graph.edge[5].weight = 5;

        graph.edge[6].source = 3;
        graph.edge[6].destination = 1;
        graph.edge[6].weight = 1;

        graph.edge[7].source = 4;
        graph.edge[7].destination = 3;
        graph.edge[7].weight = -3;

        int source = 0;
        graph.BellmanFordAlgorithm(graph, source);
    }
}
Copy The Code & Try With Live Editor

#3 Bellman Ford's Algorithm implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Define a structure to represent a directed edge
struct Edge {
    int src, dest, weight;
};

// Define a structure to represent a graph
struct Graph {
    int V, E; // Number of vertices and edges
    struct Edge* edge; // Array to store edges
};

// Function to create a graph with V vertices and E edges
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
}

// Function to print the distance array
void printDistances(int dist[], int n) {
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i  <  n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

// Bellman-Ford algorithm
void bellmanFord(struct Graph* graph, int src) {
    int V = graph->V;
    int E = graph->E;
    int dist[V];

    // Initialize distances from the source to all other vertices as INFINITE
    for (int i = 0; i  <  V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // Relax all edges V-1 times
    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;
        }
    }

    // Check for negative-weight cycles
    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]) {
            printf("Graph contains negative-weight cycle.\n");
            return;
        }
    }

    // Print the distance array
    printDistances(dist, V);
}

// Driver program to test the above functions
int main() {
    int V = 5; // Number of vertices
    int E = 8; // Number of edges
    struct Graph* graph = createGraph(V, E);

    // Edges of the graph
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;

    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;

    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;

    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;

    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;

    int src = 0; // Source vertex
    bellmanFord(graph, src);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Bellman Ford's Algorithm implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

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

class Graph {
    int V, E;
    vector < Edge> edges;

public:
    Graph(int V, int E) : V(V), E(E) {}

    void addEdge(int src, int dest, int weight) {
        edges.push_back({src, dest, weight});
    }

    void bellmanFord(int src) {
        vector<int> distance(V, numeric_limits < int>::max());
        distance[src] = 0;

        // Relax all edges V-1 times
        for (int i = 0; i  <  V - 1; ++i) {
            for (const auto& edge : edges) {
                if (distance[edge.src] != numeric_limits<int>::max() &&
                    distance[edge.src] + edge.weight < distance[edge.dest]) {
                    distance[edge.dest] = distance[edge.src] + edge.weight;
                }
            }
        }

        // Check for negative weight cycles
        for (const auto& edge : edges) {
            if (distance[edge.src] != numeric_limits < int>::max() &&
                distance[edge.src] + edge.weight < distance[edge.dest]) {
                cout << "Graph contains negative weight cycle!" << endl;
                return;
            }
        }

        // Print the distances
        cout << "Shortest distances from source " << src << " are:" << endl;
        for (int i = 0; i  <  V; ++i) {
            cout << "To vertex " << i << ": " << distance[i] << endl;
        }
    }
};

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

    Graph graph(V, E);

    cout << "Enter the edges (src, dest, weight):" << endl;
    for (int i = 0; i  <  E; ++i) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
        graph.addEdge(src, dest, weight);
    }

    int src;
    cout << "Enter the source vertex: ";
    cin >> src;

    graph.bellmanFord(src);

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Bellman Ford's Data Structure and Algorithm