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:
JUnit5 Programmatic Extension Registration with @RegisterExtension
How to Set TLS Version in Apache HttpClient
Java Program to Represent Graph Using Adjacency Matrix
LinkedHashSet trong java
Guide to the Java TransferQueue
Creating a Generic Array in Java
Compact Strings in Java 9
Spring WebClient Filters
Java Program to Implement Ternary Heap
Lấy ngày giờ hiện tại trong Java
Guide to Java 8 groupingBy Collector
Java 8 Collectors toMap
HttpClient 4 Cookbook
Java Program to Describe the Representation of Graph using Adjacency Matrix
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
TreeSet và sử dụng Comparable, Comparator trong java
Intro to Spring Boot Starters
Tìm hiểu về xác thực và phân quyền trong ứng dụng
A Guide to EnumMap
Assertions in JUnit 4 and JUnit 5
Autoboxing và Unboxing trong Java
Java Program to Describe the Representation of Graph using Incidence Matrix
Hướng dẫn Java Design Pattern – Singleton
Converting String to Stream of chars
Spring 5 and Servlet 4 – The PushBuilder
Từ khóa this và super trong Java
Derived Query Methods in Spring Data JPA Repositories
Deploy a Spring Boot WAR into a Tomcat Server
Guide to the Java Clock Class
Reactive WebSockets with Spring 5
Java Program to Implement Hash Tables chaining with Singly Linked Lists
Sending Emails with Java