package DataStructures.Graphs;
import java.util.*;
class BellmanFord
/*Implementation of Bellman ford to detect negative cycles. Graph accepts inputs in form of edges which have
start vertex, end vertes and weights. Vertices should be labelled with a number between 0 and total number of vertices-1,both inclusive*/
{
int vertex,edge;
private Edge edges[];
private int index=0;
BellmanFord(int v,int e)
{
vertex=v;
edge=e;
edges=new Edge[e];
}
class Edge
{
int u,v;
int w;
/**
*@param u Source Vertex
* @param v End vertex
* @param c Weight
*/
Edge(int a,int b,int c)
{
u=a;
v=b;
w=c;
}
}
/**
* @param p[] Parent array which shows updates in edges
* @param i Current vertex under consideration
*/
void printPath(int p[],int i)
{
if(p[i]==-1)//Found the path back to parent
return;
printPath(p,p[i]);
System.out.print(i+" ");
}
public static void main(String args[])
{
BellmanFord obj=new BellmanFord(0,0);//Dummy object to call nonstatic variables
obj.go();
}
public void go()//Interactive run for understanding the class first time. Assumes source vertex is 0 and shows distaance to all vertices
{
Scanner sc=new Scanner(System.in);//Grab scanner object for user input
int i,v,e,u,ve,w,j,neg=0;
System.out.println("Enter no. of vertices and edges please");
v=sc.nextInt();
e=sc.nextInt();
Edge arr[]=new Edge[e];//Array of edges
System.out.println("Input edges");
for(i=0;idist[arr[j].u]+arr[j].w)
{
dist[arr[j].v]=dist[arr[j].u]+arr[j].w;//Update
p[arr[j].v]=arr[j].u;
}
}
}
//Final cycle for negative checking
for(j=0;jdist[arr[j].u]+arr[j].w)
{
neg=1;
System.out.println("Negative cycle");
break;
}
if(neg==0)//Go ahead and show results of computaion
{
System.out.println("Distances are: ");
for(i=0;idist[arr[j].u]+arr[j].w)
{
dist[arr[j].v]=dist[arr[j].u]+arr[j].w;//Update
p[arr[j].v]=arr[j].u;
}
}
}
//Final cycle for negative checking
for(j=0;jdist[arr[j].u]+arr[j].w)
{
neg=1;
System.out.println("Negative cycle");
break;
}
if(neg==0)//Go ahead and show results of computaion
{
System.out.println("Distance is: "+dist[end]);
System.out.println("Path followed:");
System.out.print(source+" ");
printPath(p,end);
System.out.println();
}
}
/**
*@param x Source Vertex
* @param y End vertex
* @param z Weight
*/
public void addEdge(int x,int y,int z)//Adds unidirectionl Edge
{
edges[index++]=new Edge(x,y,z);
}
public Edge[] getEdgeArray()
{
return edges;
}
}