Java Coding Test Course, Bellman-Ford

One of the algorithms that frequently appears in coding tests is the Bellman-Ford algorithm. In this article, we will explain the concept of the Bellman-Ford algorithm, how it works, and how to apply it to real problems step by step. We have included detailed solution processes along with various examples to provide useful information for coding tests and job preparation.

Introduction to Bellman-Ford Algorithm

The Bellman-Ford algorithm is used to find the shortest path from a single source to all other vertices in a weighted graph. This algorithm allows for edges with negative weights but cannot provide the shortest path if a negative cycle exists. Therefore, it is essential to check whether a negative cycle is present in the graph before applying the algorithm.

Features of the Bellman-Ford Algorithm

  • When the number of vertices is V, the time complexity is O(VE).
  • The format of edge data can vary.
  • The shortest path can be effectively explored even in graphs without negative weights.
  • It includes built-in functionality for detecting negative cycles.

Problem: Finding the Shortest Path

The following is a problem to find the shortest path using the Bellman-Ford algorithm.

Problem Description

Given a weighted directed graph, write a program to find the shortest path from a specific starting point to all other vertices. The graph may contain negative weights. If a negative cycle exists, the message ‘Negative Cycle’ should be printed.

Input Format

The first line contains the number of vertices V (1 ≤ V ≤ 1000) and the number of edges E (1 ≤ E ≤ 10,000).
The second line contains the starting vertex S (1 ≤ S ≤ V).
The following E lines provide information about each edge in the form of u, v, w (1 ≤ u, v ≤ V, -10^5 ≤ w ≤ 10^5).

Output Format

Print the shortest path lengths to each vertex, separated by spaces.
If there is a negative cycle, print 'Negative Cycle'.

Problem Solution

1. Understanding and Analyzing the Problem

To solve the problem, we first need to understand the graph information provided in the input. We must comprehend the number of vertices and edges and the starting vertex to progress toward calculating the shortest path. This problem requires effectively applying the fundamental structure of the Bellman-Ford algorithm.

2. Algorithm Design

The Bellman-Ford algorithm proceeds through the following steps:

  1. Initialize the shortest path values based on all edges. Set the source to 0 and all other vertices to infinity.
  2. Inspect all edges for V – 1 times and update the shortest path.
  3. Recheck all edges to determine if a negative cycle exists by looking for potential updates in shortest paths.

3. Java Code Implementation

Now, let’s write the Java code based on the algorithm described above.

import java.util.*;

public class BellmanFord {
    static class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt(); // Number of vertices
        int E = sc.nextInt(); // Number of edges
        int S = sc.nextInt(); // Starting vertex

        List edges = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int weight = sc.nextInt();
            edges.add(new Edge(u, v, weight));
        }

        int[] dist = new int[V + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        // Execute the algorithm
        for (int i = 1; i <= V - 1; i++) {
            for (Edge edge : edges) {
                if (dist[edge.u] != Integer.MAX_VALUE && 
                    dist[edge.u] + edge.weight < dist[edge.v]) {
                    dist[edge.v] = dist[edge.u] + edge.weight;
                }
            }
        }

        // Detect negative cycles
        for (Edge edge : edges) {
            if (dist[edge.u] != Integer.MAX_VALUE && 
                dist[edge.u] + edge.weight < dist[edge.v]) {
                System.out.println("Negative Cycle");
                return;
            }
        }

        // Output shortest paths
        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("Infinity ");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }
}

4. Code Explanation

The code above encapsulates the entire flow of the Bellman-Ford algorithm:

  • First, we use the edge list to store all edge data.
  • We declare a distance array (dist) and initialize the distance of the starting point to 0.
  • In the inner loop, we iterate through each edge to update the shortest distance.
  • After reviewing all edges again, we check for the presence of negative cycles.

5. Testing and Validation

After completing the code, it is essential to verify the correct functioning of the algorithm through various test cases. For example:

Input:
5 8
1
1 2 4
1 3 3
2 3 1
3 2 -1
2 4 2
3 4 5
4 5 -3
5 4 2

Output:
0 3 3 5 Infinity

6. Conclusion

The Bellman-Ford algorithm is a highly useful tool for solving the shortest path problem. Its ability to accommodate negative weights allows it to be applied to various graph problems. Understanding and implementing this algorithm is one of the essential skills for achieving high scores in coding interviews and algorithm exams.

Closing

I hope this course on the Bellman-Ford algorithm has been helpful. I wish it can contribute practically to your coding test preparation. Continue to deepen your learning by applying the algorithm to various problems!