This is a java program to find shortest path from a single vertex. 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.[1] It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as 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 Use the Bellman-Ford Algorithm to Find the Shortest Path Between Two Vertices Assuming that Negative Size Edges Exist in the Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.graph; 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 destination, 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++) { if (vertex == destination) System.out.println("distance of source " + source + " to " + vertex + " is " + distances[vertex]); } } public static void main(String... arg) { int numberofvertices = 0; int source, destination; 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(); System.out.println("Enter the destination vertex: "); destination = scanner.nextInt(); BellmanFord bellmanford = new BellmanFord(numberofvertices); bellmanford.BellmanFordEvaluation(source, destination, adjacencymatrix); scanner.close(); } }
Output:
$ javac BellmanFord.java $ java BellmanFord Output: 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 Enter the destination vertex: 4 distance of source 1 to 4 is -6
Related posts:
Adding Parameters to HttpClient Requests
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
Java Program to Find Transitive Closure of a Graph
Retrieve User Information in Spring Security
Guide to the Volatile Keyword in Java
Hướng dẫn sử dụng Java Reflection
Mảng (Array) trong Java
Java Program to Implement Shoelace Algorithm
Java 8 Collectors toMap
A Guide to BitSet in Java
Hướng dẫn sử dụng Lớp FilePermission trong java
Java Copy Constructor
Java Program to Implement Bubble Sort
Spring Security – security none, filters none, access permitAll
Java Program to Implement Doubly Linked List
Tính kế thừa (Inheritance) trong java
Inheritance with Jackson
Working with Network Interfaces in Java
Java Program to Check for balanced parenthesis by using Stacks
Comparing Objects in Java
Intro to Inversion of Control and Dependency Injection with Spring
Java Program to add two large numbers using Linked List
Convert Time to Milliseconds in Java
Introduction to Spring Security Expressions
Java Program to Find Strongly Connected Components in Graphs
Java Program to Implement Naor-Reingold Pseudo Random Function
Spring Boot - Enabling HTTPS
Java Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree
Service Registration with Eureka
Java Program to Implement Sieve Of Sundaram
A Guide to TreeMap in Java