Mastering Graph Algorithms: BFS, DFS, Dijkstra, Floyd-Warshall, and Bellman-Ford in Java

Chapter 5: Bellman-Ford Algorithm in Java

The Bellman-Ford Algorithm is a powerful graph algorithm used to find the shortest path from a single source to all other vertices — even when negative weight edges are present.

Unlike Dijkstra’s Algorithm, Bellman-Ford can handle negative weights and even detect negative weight cycles in a graph. It works by repeatedly relaxing all edges up to V - 1 times, where V is the number of vertices.

If after these V-1 passes, you can still relax any edge — a negative cycle exists, and the algorithm reports it. This makes Bellman-Ford useful not just for pathfinding, but also for validating financial systems (like detecting arbitrage).

2. Bellman-Ford Coding (with 2 Examples)

a. Syllabus-Oriented Example (Shortest Path with Negative Weights)

import java.util.*;

public class BellmanFordExample {

    static class Edge {

        int src, dest, weight;

        Edge(int s, int d, int w) {

            src = s;

            dest = d;

            weight = w;

        }

    }

    public static void bellmanFord(List<Edge> edges, int V, int source) {

        int[] dist = new int[V];

        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[source] = 0;

        // Step 1: Relax all edges V-1 times

        for (int i = 1; i < V; i++) {

            for (Edge edge : edges) {

                if (dist[edge.src] != Integer.MAX_VALUE &&

                    dist[edge.src] + edge.weight < dist[edge.dest]) {

                    dist[edge.dest] = dist[edge.src] + edge.weight;

                }

            }

        }

        // Step 2: Check for negative-weight cycles

        for (Edge edge : edges) {

            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;

            }

        }

        System.out.println("Vertex distances from source " + source + ":");

        for (int i = 0; i < V; i++) {

            System.out.println("To " + i + " → " + (dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]));

        }

    }

    public static void main(String[] args) {

        int V = 5;

        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(0, 1, -1));

        edges.add(new Edge(0, 2, 4));

        edges.add(new Edge(1, 2, 3));

        edges.add(new Edge(1, 3, 2));

        edges.add(new Edge(1, 4, 2));

        edges.add(new Edge(3, 2, 5));

        edges.add(new Edge(3, 1, 1));

        edges.add(new Edge(4, 3, -3));

        bellmanFord(edges, V, 0);

    }

}

b. Real-World Example: Currency Arbitrage Detection

In financial markets, negative cycles in currency exchange rates represent arbitrage opportunities — where a trader could profit by cycling through multiple currencies.

// Example: Currency exchange graph

// USD → EUR → JPY → USD

// We convert exchange rates to log space: weight = -log(rate)

// A negative cycle means: profit opportunity exists.

Edge("USD", "EUR", -Math.log(0.85));

Edge("EUR", "JPY", -Math.log(129.7));

Edge("JPY", "USD", -Math.log(0.0092));

// Detecting if a negative cycle exists tells if arbitrage is possible.

(Note: Full implementation involves mapping currencies to integers and back, and working in logarithmic space.)

3. Pros of Bellman-Ford Algorithm

• ✅ Handles negative edge weights safely.
• ✅ Can detect negative weight cycles — Dijkstra can’t.
• ✅ Conceptually simple and works for both directed and undirected graphs.
• ✅ Suitable for sparse graphs and financial systems.
• ✅ Easy to modify for various shortest-path problems.

4. Cons of Bellman-Ford Algorithm

• ❌ Slower than Dijkstra’s — time complexity is O(V × E).
• ❌ Not efficient for dense graphs or real-time usage.
• ❌ Higher chance of redundancy — many edge relaxations are unnecessary.
• ❌ Doesn’t give all-pairs shortest paths — only single-source.
• ❌ Slightly more complex to debug due to the cycle-check logic.

5. How Bellman-Ford Is Better Than Other Algorithms

• Better than Dijkstra in handling negative weights and detecting cycles.
• Better than BFS/DFS for shortest path in weighted graphs.
• More flexible than Floyd-Warshall for sparse graphs when only a single source matters.
• Offers both shortest path calculation and cycle detection in one pass.

6. Best-Case Scenarios to Use Bellman-Ford

• Graphs with negative weights (e.g., cost reductions, currency exchanges).
• Detecting arbitrage opportunities in finance.
• Validating routing protocols like RIP (Routing Information Protocol).
• Graphs where negative cycle detection is more important than speed.
• Sparse graphs with fewer edges per vertex.

7. Applications of Bellman-Ford Algorithm

• Financial systems: Currency trading, arbitrage detection.
• Telecom routing protocols: RIP uses a version of Bellman-Ford.
• Social networks: Influence/cost propagation with negative scores.
• Transportation systems: Cost discounts or penalties in certain paths.
• AI & Machine Learning: Cost graph analysis in optimization.

8. Worst-Case Scenarios to Use Bellman-Ford

• Large, dense graphs with thousands of edges — too slow.
• Graphs where all edges are non-negative — Dijkstra is faster.
• Real-time systems needing quick responses.
• When you need all-pairs shortest paths — Floyd-Warshall is better.
• Games or simulations where frame rate performance matters.