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:
Transactions with Spring and JPA
Phân biệt JVM, JRE, JDK
Spring Data JPA and Null Parameters
Guide to UUID in Java
Jackson – Marshall String to JsonNode
@Before vs @BeforeClass vs @BeforeEach vs @BeforeAll
Guide to @JsonFormat in Jackson
Java Program to Implement Control Table
Java – Convert File to InputStream
OAuth 2.0 Resource Server With Spring Security 5
Java Program to Implement D-ary-Heap
Spring Boot - Admin Server
Java Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure)
Guide to Spring Cloud Kubernetes
Spring Boot With H2 Database
Java Program to Implement Circular Doubly Linked List
Hướng dẫn Java Design Pattern – Dependency Injection
Java 8 Stream API Analogies in Kotlin
Jackson vs Gson
Send an email using the SMTP protocol
Handling Errors in Spring WebFlux
Deploy a Spring Boot App to Azure
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Java Program to Implement PriorityQueue API
Inject Parameters into JUnit Jupiter Unit Tests
Spring Boot - Cloud Configuration Server
New Features in Java 8
Spring Boot - Application Properties
Quick Guide to Spring Controllers
Lớp LinkedHashMap trong Java
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
An Intro to Spring Cloud Contract