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:
Apache Commons Collections MapUtils
A Guide to JPA with Spring
Java Program to Implement Aho-Corasick Algorithm for String Matching
An Example of Load Balancing with Zuul and Eureka
Java equals() and hashCode() Contracts
Spring Security Authentication Provider
Netflix Archaius with Various Database Configurations
Basic Authentication with the RestTemplate
Hướng dẫn sử dụng lớp Console trong java
TreeSet và sử dụng Comparable, Comparator trong java
Java Program to Implement the Vigenere Cypher
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Mệnh đề Switch-case trong java
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Java Program to Implement vector
Spring Boot - Eureka Server
Java Program to Implement Kosaraju Algorithm
Java Program to Implement Skip List
Partition a List in Java
Returning Image/Media Data with Spring MVC
Java String Conversions
Java Program to Implement Adjacency Matrix
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Checked and Unchecked Exceptions in Java
Guide to java.util.concurrent.Future
Documenting a Spring REST API Using OpenAPI 3.0
Tìm hiểu cơ chế Lazy Evaluation của Stream trong Java 8
Java Program to Implement Bresenham Line Algorithm
Spring MVC Custom Validation
Java Program to Generate Random Numbers Using Middle Square Method
Spring REST API with Protocol Buffers
Convert a Map to an Array, List or Set in Java