Java Bellman-Ford Algorithm

Welcome to this comprehensive Java tutorial on the Bellman-Ford Algorithm! In this lesson, we'll learn about this powerful algorithm used for finding the shortest paths in a weighted directed graph with negative edge weights. Let's dive in!

What is the Bellman-Ford Algorithm?

💡 Pro Tip: The Bellman-Ford Algorithm is a versatile tool for finding the shortest path from a single source vertex to all other vertices in a graph, even when the graph contains negative edge weights.

In simpler terms, the Bellman-Ford Algorithm is an algorithm that helps us determine the shortest path between nodes in a graph with multiple edges and negative edge weights. Let's break it down!

Understanding Graphs and Shortest Paths

Before diving into the Bellman-Ford Algorithm, let's take a moment to understand what a graph is and the concept of shortest paths.

A graph is a set of nodes (also known as vertices) connected by edges. In a directed graph, the edges have a direction, meaning they go from one node to another.

The shortest path between two nodes in a graph is the path with the least total edge weight.

Bellman-Ford Algorithm Steps

The Bellman-Ford Algorithm consists of V-1 relaxation iterations, where V is the number of vertices in the graph. Here are the steps involved:

Initialize the distance of each vertex from the source vertex to infinity, except for the source vertex itself, which is set to 0.
Run V-1 iterations, where each iteration performs the following steps:
- Relax all edges. For each edge (u, v), if the current distance to u plus the edge weight is less than the current distance to v, update the distance to v.
Run one final pass to check for negative-weight cycles. If any vertex's distance is updated during this pass, there exists a negative-weight cycle in the graph.

📝 Note: If there are no negative-weight cycles, the final distances calculated will represent the shortest paths from the source vertex to all other vertices.

Implementing the Bellman-Ford Algorithm in Java

Now that we've covered the theory, let's implement the Bellman-Ford Algorithm in Java!

Here's a complete, working example of the Bellman-Ford Algorithm implementation:

java

import java.util.*;

public class BellmanFord {
    private static final int INF = Integer.MAX_VALUE;

    private int[] distances;
    private List<List<Edge>> adjacencyList;

    public BellmanFord(int vertices, List<Edge> edges) {
        this.distances = new int[vertices];
        this.adjacencyList = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>());
            distances[i] = INF;
        }

        for (Edge edge : edges) {
            adjacencyList.get(edge.from).add(edge);
        }
    }

    public void bellmanFord(int source) {
        distances[source] = 0;

        for (int i = 1; i < distances.length - 1; i++) {
            for (int vertex = 0; vertex < distances.length; vertex++) {
                for (Edge edge : adjacencyList.get(vertex)) {
                    if (distances[vertex] != INF && distances[vertex] + edge.weight < distances[edge.to]) {
                        distances[edge.to] = distances[vertex] + edge.weight;
                    }
                }
            }
        }

        for (int vertex = 0; vertex < distances.length; vertex++) {
            for (Edge edge : adjacencyList.get(vertex)) {
                if (distances[vertex] != INF && distances[vertex] + edge.weight < distances[edge.to]) {
                    System.out.println("Graph contains a negative-weight cycle.");
                    return;
                }
            }
        }
    }

    public static class Edge {
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        BellmanFord bellmanFord = new BellmanFord(6, Arrays.asList(
                new BellmanFord.Edge(0, 1, 10),
                new BellmanFord.Edge(0, 2, 5),
                new BellmanFord.Edge(0, 4, -1),
                new BellmanFord.Edge(1, 2, 3),
                new BellmanFord.Edge(1, 3, 6),
                new BellmanFord.Edge(1, 4, -2),
                new BellmanFord.Edge(2, 3, 1),
                new BellmanFord.Edge(2, 4, 2),
                new BellmanFord.Edge(3, 4, -1),
                new BellmanFord.Edge(4, 5, 9)
        ));

        bellmanFord.bellmanFord(0);

        System.out.println("Shortest distances from vertex 0 to all other vertices:");
        for (int i = 0; i < bellmanFord.distances.length; i++) {
            System.out.println("Vertex " + i + " : " + bellmanFord.distances[i]);
        }
    }
}

🎯 Quiz: What does the Bellman-Ford Algorithm do?

A: Finds the shortest path between two nodes in a graph B: Finds the shortest path from a single source vertex to all other vertices in a graph with multiple edges and negative edge weights C: Finds the longest path from a single source vertex to all other vertices in a graph with multiple edges and negative edge weights

Correct: B