Bellman Ford Display predecessor for every iterations
<p>Here the predecessor vertices get displayed for all iterations. I want the final predecessor to be displayed for the vertices</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)
                     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;
                        /*Gives me the predecessor nodes of all iterations How can i get the final predecessornodes*/                                                                                                     System.out.println(edges.get(j).v+" Has predecessor " + edges.get(j).u);
                     }
        }
        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+"to"+i+" ==&gt; "+r.d[i]);
             else
             System.out.println(" There is a nagative edge cycle ");
       }
}
</code></pre>

<p>The erronous output is as follows. I am trying to print out the predecessor for every iterations:</p>

<pre><code>**OUTPUT:**

Enter number of vertices
Cost Matrix
0
-1
4
0
0
0
0
3
2
2
0
0
0
0
0
0
1
5
0
0
0
0
0
-3
0
Enter the source vertex
1 Has predecessor 0
2 Has predecessor 0
2 Has predecessor 1
3 Has predecessor 1
4 Has predecessor 1
3 Has predecessor 4
0to0 ==&gt; 0
0to1 ==&gt; -1
0to2 ==&gt; 2
0to3 ==&gt; -2
0to4 ==&gt; 1
</code></pre>
