Simple Java Program for Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest paths from a single source vertex to all other vertices in a graph. It can handle negative weights and detect negative weight cycles.

Java Code

import java.util.*;

class BellmanFord {
    private int vertices; // Number of vertices in the graph
    private List<Edge> edges; // List of all edges in the graph

    // Edge class to represent a graph edge
    static class Edge {
        int source, destination, weight;

        Edge(int source, int destination, int weight) {
            this.source = source;
            this.destination = destination;
            this.weight = weight;
        }
    }

    // Graph constructor
    public BellmanFord(int vertices) {
        this.vertices = vertices;
        edges = new ArrayList<>();
    }

    // Method to add an edge to the graph
    public void addEdge(int source, int destination, int weight) {
        edges.add(new Edge(source, destination, weight));
    }

    // Bellman-Ford algorithm
    public void bellmanFord(int startVertex) {
        int[] distances = new int[vertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[startVertex] = 0;

        // Relax all edges |V| - 1 times
        for (int i = 1; i < vertices; i++) {
            for (Edge edge : edges) {
                int u = edge.source;
                int v = edge.destination;
                int weight = edge.weight;
                if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                }
            }
        }

        // Check for negative-weight cycles
        for (Edge edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int weight = edge.weight;
            if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
                System.out.println("Graph contains a negative weight cycle.");
                return;
            }
        }

        // Print shortest distances
        System.out.println("Shortest distances from vertex " + startVertex);
        for (int i = 0; i < vertices; i++) {
            System.out.println("To vertex " + i + " - " + (distances[i] == Integer.MAX_VALUE ? "Infinity" : distances[i]));
        }
    }

    public static void main(String[] args) {
        int vertices = 5; // Total number of vertices in the graph
        BellmanFord graph = new BellmanFord(vertices);
        graph.addEdge(0, 1, -1);
        graph.addEdge(0, 2, 4);
        graph.addEdge(1, 2, 3);
        graph.addEdge(1, 3, 2);
        graph.addEdge(1, 4, 2);
        graph.addEdge(3, 2, 5);
        graph.addEdge(3, 1, 1);
        graph.addEdge(4, 3, -3);

        graph.bellmanFord(0);
    }
}

Breaking Down the Code

1. Edge Class: Representing Graph Edges

static class Edge {
    int source, destination, weight;

    Edge(int source, int destination, int weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
    }
}

• Fields: source, destination, and weight represent the starting node, ending node, and weight of the edge, respectively.
• Constructor: Initializes the edge with given values.

2. Graph Initialization: Setting Up the Graph

private int vertices; // Number of vertices in the graph
private List<Edge> edges; // List of all edges in the graph

public BellmanFord(int vertices) {
    this.vertices = vertices;
    edges = new ArrayList<>();
}

• vertices: Holds the number of vertices in the graph.
• edges: Stores all the edges of the graph.
• Constructor: Initializes the graph with the given number of vertices and creates an empty list of edges.

3. addEdge Method: Adding Edges

public void addEdge(int source, int destination, int weight) {
    edges.add(new Edge(source, destination, weight));
}

• addEdge: Adds an edge to the list of edges in the graph.

4. bellmanFord Method: Finding Shortest Paths

public void bellmanFord(int startVertex) {
    int[] distances = new int[vertices];
    Arrays.fill(distances, Integer.MAX_VALUE);
    distances[startVertex] = 0;

    // Relax all edges |V| - 1 times
    for (int i = 1; i < vertices; i++) {
        for (Edge edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int weight = edge.weight;
            if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
            }
        }
    }

    // Check for negative-weight cycles
    for (Edge edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int weight = edge.weight;
        if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
            System.out.println("Graph contains a negative weight cycle.");
            return;
        }
    }

    // Print shortest distances
    System.out.println("Shortest distances from vertex " + startVertex);
    for (int i = 0; i < vertices; i++) {
        System.out.println("To vertex " + i + " - " + (distances[i] == Integer.MAX_VALUE ? "Infinity" : distances[i]));
    }
}

• distances: An array to store the shortest distances from the start vertex to all other vertices, initialized to infinity (Integer.MAX_VALUE) except for the start vertex which is set to 0.
• Relaxation Loop: For each vertex, relax all edges. If a shorter path is found, update the shortest known distance.
• Negative Cycle Check: After relaxing all edges (V-1) times, check for negative-weight cycles by seeing if any edge can still be relaxed.
• Print Distances: Print the shortest distances from the start vertex to all other vertices.

5. Main Method: Running the Algorithm

public static void main(String[] args) {
    int vertices = 5; // Total number of vertices in the graph
    BellmanFord graph = new BellmanFord(vertices);
    graph.addEdge(0, 1, -1);
    graph.addEdge(0, 2, 4);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 2);
    graph.addEdge(1, 4, 2);
    graph.addEdge(3, 2, 5);
    graph.addEdge(3, 1, 1);
    graph.addEdge(4, 3, -3);

    graph.bellmanFord(0);
}

• vertices: Number of vertices in the graph.
• graph.addEdge: Adds edges with their respective weights to the graph.
• graph.bellmanFord(0): Calls the Bellman-Ford algorithm starting from vertex 0 and prints the shortest distances.

Conclusion

The Bellman-Ford algorithm is a powerful method for finding shortest paths in graphs with negative weights. This program not only finds the shortest paths but also detects if a negative-weight cycle exists in the graph. With this understanding, you can now handle more complex graphs and adapt the algorithm to different scenarios.

Feel free to experiment with different graphs and edge weights to see how the algorithm behaves. Happy coding!