ここでは、すべての反復で先行する頂点が表示されます。頂点の最後の先行を表示したい
import java.io.*;
import java.util.*;
public class BellmanFord {
LinkedList<Edge> 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<Edge>();
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<n;i++)
for(int j=0;j<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<n;++i)
d[i]=INFINITY;;
d[s] = 0;
for (i = 0; i < n - 1; ++i)
for (j = 0; j < e; ++j)
if (d[edges.get(j).u] + edges.get(j).w < 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 < e; ++j)
if (d[edges.get(j).u] + edges.get(j).w < 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<r.n;i++)
System.out.println(r.s+"to"+i+" ==> "+r.d[i]);
else
System.out.println(" There is a nagative edge cycle ");
}
}
誤った出力は次のとおりです。私はすべての反復について前任者を印刷しようとしています:
**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 ==> 0
0to1 ==> -1
0to2 ==> 2
0to3 ==> -2
0to4 ==> 1