Bellman-Ford Algorithm in Java: Handling Graphs with Negative Weights ??

Introduction

The Bellman-Ford algorithm is a fundamental shortest path algorithm that works for graphs with negative weight edges. Unlike Dijkstra’s algorithm, it can handle graphs with negative weights and detect negative weight cycles. This makes it particularly useful in scenarios like currency arbitrage and network routing.

Algorithm Explanation

The Bellman-Ford algorithm works as follows:

1. Initialize distances from the source to all vertices as infinite (∞), except for the source itself, which is set to 0.
2. Relax all edges |V| - 1 times (where |V| is the number of vertices). This ensures the shortest possible distances are calculated.
3. Perform one more relaxation to check for negative weight cycles. If a distance can still be updated, a negative weight cycle exists.

Java Implementation

Below is the Java implementation of the Bellman-Ford algorithm:

import java.util.Arrays;

class Edge {
    int src, dest, weight;
    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

public class BellmanFord {
    int vertices, edges;
    Edge[] edgeList;

    public BellmanFord(int vertices, int edges) {
        this.vertices = vertices;
        this.edges = edges;
        edgeList = new Edge[edges];
    }

    void findShortestPath(int src) {
        int[] dist = new int[vertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        // Relax all edges |V| - 1 times
        for (int i = 0; i < vertices - 1; i++) {
            for (Edge edge : edgeList) {
                if (dist[edge.src] != Integer.MAX_VALUE && dist[edge.src] + edge.weight < dist[edge.dest]) {
                    dist[edge.dest] = dist[edge.src] + edge.weight;
                }
            }
        }

        // Check for negative weight cycles
        for (Edge edge : edgeList) {
            if (dist[edge.src] != Integer.MAX_VALUE && dist[edge.src] + edge.weight < dist[edge.dest]) {
                System.out.println("Graph contains a negative weight cycle!");
                return;
            }
        }

        // Print shortest distances
        System.out.println("Vertex distances from source:");
        for (int i = 0; i < vertices; i++) {
            System.out.println("Vertex " + i + ": " + (dist[i] == Integer.MAX_VALUE ? "∞" : dist[i]));
        }
    }

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

        // Adding edges
        graph.edgeList[0] = new Edge(0, 1, -1);
        graph.edgeList[1] = new Edge(0, 2, 4);
        graph.edgeList[2] = new Edge(1, 2, 3);
        graph.edgeList[3] = new Edge(1, 3, 2);
        graph.edgeList[4] = new Edge(1, 4, 2);
        graph.edgeList[5] = new Edge(3, 2, 5);
        graph.edgeList[6] = new Edge(3, 1, 1);
        graph.edgeList[7] = new Edge(4, 3, -3);

        graph.findShortestPath(0);
    }
}
        

Complexity Analysis

• Time Complexity: O(VE)as we relax all edges for V?1 times.
• Space Complexity: O(V), since we maintain distance arrays.

Conclusion ??

The Bellman-Ford algorithm is a powerful tool for computing shortest paths in graphs with negative weights. Unlike Dijkstra’s algorithm, it can handle negative weights and even detect negative weight cycles.