Java Program to Implement Bellman Ford Algorithm

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.

  1. import java.util.Scanner;
  2.  
  3. public class BellmanFord
  4. {
  5.     private int distances[];
  6.     private int numberofvertices;
  7.     public static final int MAX_VALUE = 999;
  8.  
  9.     public BellmanFord(int numberofvertices)
  10.     {
  11.         this.numberofvertices = numberofvertices;
  12.         distances = new int[numberofvertices + 1];
  13.     }
  14.  
  15.     public void BellmanFordEvaluation(int source, int adjacencymatrix[][])
  16.     {
  17.         for (int node = 1; node <= numberofvertices; node++)
  18.         {
  19.             distances[node] = MAX_VALUE;
  20.         }
  21.  
  22.         distances[source] = 0;
  23.         for (int node = 1; node <= numberofvertices - 1; node++)
  24.         {
  25.             for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
  26.             {
  27.                 for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
  28.                 {
  29.                     if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
  30.                     {
  31.                         if (distances[destinationnode] > distances[sourcenode] 
  32.                                 + adjacencymatrix[sourcenode][destinationnode])
  33.                             distances[destinationnode] = distances[sourcenode]
  34.                                 + adjacencymatrix[sourcenode][destinationnode];
  35.                     }
  36.                 }
  37.             }
  38.         }
  39.  
  40.         for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
  41.         {
  42.             for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
  43.             {
  44.                 if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
  45.                 {
  46.                     if (distances[destinationnode] > distances[sourcenode]
  47.                            + adjacencymatrix[sourcenode][destinationnode])
  48.                         System.out.println("The Graph contains negative egde cycle");
  49.                 }
  50.             }
  51.         }
  52.  
  53.         for (int vertex = 1; vertex <= numberofvertices; vertex++)
  54.         {
  55.             System.out.println("distance of source  " + source + " to "
  56.                       + vertex + " is " + distances[vertex]);
  57.         }
  58.     }
  59.  
  60.     public static void main(String... arg)
  61.     {
  62.         int numberofvertices = 0;
  63.         int source;
  64.         Scanner scanner = new Scanner(System.in);
  65.  
  66.         System.out.println("Enter the number of vertices");
  67.         numberofvertices = scanner.nextInt();
  68.  
  69.         int adjacencymatrix[][] = new int[numberofvertices + 1][numberofvertices + 1];
  70.         System.out.println("Enter the adjacency matrix");
  71.         for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
  72.         {
  73.             for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
  74.             {
  75.                 adjacencymatrix[sourcenode][destinationnode] = scanner.nextInt();
  76.  	        if (sourcenode == destinationnode)
  77.                 {
  78.                     adjacencymatrix[sourcenode][destinationnode] = 0;
  79.                     continue;
  80.                 }
  81.                 if (adjacencymatrix[sourcenode][destinationnode] == 0)
  82.                 {
  83.                     adjacencymatrix[sourcenode][destinationnode] = MAX_VALUE;
  84.                 }
  85.             }
  86.         }
  87.  
  88.         System.out.println("Enter the source vertex");
  89.         source = scanner.nextInt();
  90.  
  91.         BellmanFord bellmanford = new BellmanFord(numberofvertices);
  92.         bellmanford.BellmanFordEvaluation(source, adjacencymatrix);
  93.         scanner.close();	
  94.     }
  95. }

$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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.