Java Program to Find the Shortest Path using Bellmanford Algorithm

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.

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

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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.