title: Bellman Ford Algorithm in Java
body: <p>Can Anyone help with bellman ford algorithm in java to calculate the shortest path from the source vertex.</p>
  
  <p>I would also like the final updated predecessor nodes to be printed for each nodes after traversing all the edges and after all iterations
       This is my code</p>
  
  <pre><code>import java.io.*;
  import java.util.*;
  public class BellmanFord {
      LinkedList&lt;Edge&gt; edges;
      int d[];
      int n,e,s;
      final int INFINITY=999;
  
      private static class Edge  {
          int u,v,w;
  
          public Edge(int a, int b, int c)     {
              u=a;
              v=b;
              w=c;
          }
      }
  
      BellmanFord() throws IOException {
          int item;
          edges = new LinkedList&lt;Edge&gt;();
          BufferedReader inp = new BufferedReader (new InputStreamReader(System.in));
  
          System.out.print("Enter number of vertices ");
          n = Integer.parseInt(inp.readLine());
  
          System.out.println("Cost Matrix");
          for(int i=0;i&lt;n;i++) {
              for(int j=0;j&lt;n;j++)   {
                  item = Integer.parseInt(inp.readLine());
                  if(item != 0)
                      edges.add(new Edge(i,j,item));
              }
          }
  
          e = edges.size();
          d = new int[n];
  
          System.out.print("Enter the source vertex ");
          s = Integer.parseInt(inp.readLine());
      }
  
      void relax() {
          int i,j;
          for(i=0;i&lt;n;++i)
              d[i]=INFINITY;
  
          d[s] = 0;
          for (i = 0; i &lt; n - 1; ++i) {
              for (j = 0; j &lt; e; ++j) { //here i am calculating the shortest path
                  if (d[edges.get(j).u] + edges.get(j).w &lt; d[edges.get(j).v]) {
                      d[edges.get(j).v] = d[edges.get(j).u] + edges.get(j).w;
                  }
               }
           }
      }
  
      boolean cycle() {
          int j;
          for (j = 0; j &lt; e; ++j)
              if (d[edges.get(j).u] + edges.get(j).w &lt; d[edges.get(j).v])
                   return false;
          return true;
      }
  
      public static void main(String args[]) throws IOException   {
          BellmanFord r = new BellmanFord();
          r.relax();
          if(r.cycle()) {
              for(int i=0;i&lt;r.n;i++)
                  System.out.println(r.s+" ==&gt; "+r.d[i]);
          } else {
              System.out.println(" There is a negative edge cycle ");
          }
      }
  }
  </code></pre>