This Java program is to Implement Bellman-Ford algorithm.The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.It is capable of handling graphs in which some of the edge weights are negative numbers.
Here is the source code of the Java program to implement Bellman-Ford. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.Scanner; public class BellmanFord { private int distances[]; private int numberofvertices; public static final int MAX_VALUE = 999; public BellmanFord(int numberofvertices) { this.numberofvertices = numberofvertices; distances = new int[numberofvertices + 1]; } public void BellmanFordEvaluation(int source, int adjacencymatrix[][]) { for (int node = 1; node <= numberofvertices; node++) { distances[node] = MAX_VALUE; } distances = 0; for (int node = 1; node <= numberofvertices - 1; node++) { for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++) { for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++) { if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE) { if (distances[destinationnode] > distances[sourcenode] + adjacencymatrix[sourcenode][destinationnode]) distances[destinationnode] = distances[sourcenode] + adjacencymatrix[sourcenode][destinationnode]; } } } } for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++) { for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++) { if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE) { if (distances[destinationnode] > distances[sourcenode] + adjacencymatrix[sourcenode][destinationnode]) System.out.println("The Graph contains negative egde cycle"); } } } for (int vertex = 1; vertex <= numberofvertices; vertex++) { System.out.println("distance of source " + source + " to " + vertex + " is " + distances[vertex]); } } public static void main(String... arg) { int numberofvertices = 0; int source; Scanner scanner = new Scanner(System.in); System.out.println("Enter the number of vertices"); numberofvertices = scanner.nextInt(); int adjacencymatrix[][] = new int[numberofvertices + 1][numberofvertices + 1]; System.out.println("Enter the adjacency matrix"); for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++) { for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++) { adjacencymatrix[sourcenode][destinationnode] = scanner.nextInt(); if (sourcenode == destinationnode) { adjacencymatrix[sourcenode][destinationnode] = 0; continue; } if (adjacencymatrix[sourcenode][destinationnode] == 0) { adjacencymatrix[sourcenode][destinationnode] = MAX_VALUE; } } } System.out.println("Enter the source vertex"); source = scanner.nextInt(); BellmanFord bellmanford = new BellmanFord(numberofvertices); bellmanford.BellmanFordEvaluation(source, adjacencymatrix); scanner.close(); } }
$javac BellmanFord.java $java BellmanFord Enter the number of vertices 6 Enter the adjacency matrix 0 4 0 0 -1 0 0 0 -1 0 -2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -5 0 3 0 0 0 0 0 0 Enter the source vertex 1 distance of source 1 to 1 is 0 distance of source 1 to 2 is 4 distance of source 1 to 3 is 3 distance of source 1 to 4 is -6 distance of source 1 to 5 is -1 distance of source 1 to 6 is 2
Related posts:
Java Program to Implement Weight Balanced Tree
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Java Program to Implement ArrayList API
Introduction to PCollections
Exploring the Spring Boot TestRestTemplate
A Guide to LinkedHashMap in Java
Add Multiple Items to an Java ArrayList
Java Program to do a Depth First Search/Traversal on a graph non-recursively
Java Program to Implement AA Tree
Java Program to Find MST (Minimum Spanning Tree) using Kruskal’s Algorithm
Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach
Introduction to the Java ArrayDeque
Multi Dimensional ArrayList in Java
Java Program to Implement Control Table
Lớp HashMap trong Java
A Custom Media Type for a Spring REST API
Introduction to Spring Cloud OpenFeign
Guide to CopyOnWriteArrayList
Tính kế thừa (Inheritance) trong java
Jackson Annotation Examples
Filtering a Stream of Optionals in Java
Java Program to Implement Unrolled Linked List
Guide to BufferedReader
A Guide To UDP In Java
Java Program to Implement Adjacency List
Immutable ArrayList in Java
Spring Boot - Eureka Server
Spring – Injecting Collections
Java Program to Implement Sieve Of Sundaram
Java Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree
Summing Numbers with Java Streams
Java Program to Implement Park-Miller Random Number Generation Algorithm