import java.util.*;import java.io.*;import graph.*;import java.awt.*;/** * Description:	This file contains a version of Bellman-Ford algorithm. * @author	Brenda Ashmore * @version	April 4, 2001 *  */public class bellmanford{   static DirectedWeightedGraph g;		   private static boolean bellmanford() throws Exception    {      int n = g.getVertexListSize();	// The number of vertices in graph      int i = 0;			// a counter      ArrayList Edges = g.getEdgeList();// the edges of the graph      WeightedEdge e;				// for each edge in Edges            // INITIALIZE-SINGLE-SOURCE      int [] D = new int [n+1];		// an array of distances from source      int [] Pi = new int [n+1];	// an array of predecessors         				// We'll ignore D[0] and Pi[0].      for (i=1; i<=n; i++)      {         D[i] = 10000;			// Initialize each distance to infinity         Pi[i] = -1;			// Initialize predecessors to             					// nonexistent vertex, -1.      }      D[1] = 0;	// The distance from the source to itself is zero.                       g.getVertex(1).setColor(Color.red);	// Color the source vertex red.                        // RELAX      for (i=1; i<n; i++)      {            for (int j=0; j<Edges.size(); j++)	// For the number of edges         {              // Get the jth edge in Edges.            e = (WeightedEdge) Edges.get(j);                        Vertex es = e.getStart();		// es = first V of edge e            Vertex ee = e.getEnd();		// ee = second V of edge e                        int u = g.getVertexList().indexOf(es) +1;	// u = index of es + 1            int v = g.getVertexList().indexOf(ee) +1;	// v = index of ee + 1                            // Check to see if path with intermediate vertex, u, is shorter            // than current shortest path.            if ( D[v] > D[u] + e.getEdgeWeight())            {               D[v] = D[u] + e.getEdgeWeight();	//                                              // If there was a valid predeccessor before this, unbold that                // edge.               if(Pi[v] != -1)               {                  g.getEdge(Pi[v], v).setBold(false);               }                              // Set the current edge to bold.               e.setBold(true);                              // Set the new predeccessor.               Pi[v] = u;            }                     }          g.Wait();	// At the end of each pass, wait for user to continue.      }            // CHECK FOR NEGATIVE CYCLE.      for (int j=0; j<Edges.size(); j++)      {         // Get the jth edge in Edges.         e = (DirectedWeightedEdge) Edges.get(j);         Vertex es = e.getStart();	// es = first V of edge e         Vertex ee = e.getEnd();	// ee = second V of edge e                     int u = g.getVertexList().indexOf(es) + 1;	// u = index of es +          int v = g.getVertexList().indexOf(ee) + 1;	// v = index of ee + 1                  if (D[v] > D[u] + Utils.getEdgeWeight(g,u,v,10000) )         {            System.out.println("A negative cycle has been found.");            return false;		// A negative cycle has been found          }	      }            return true;			// No negative cycle was found.   }	           // The main function creates a graph and then calls the Bellman-Ford   // algorithm.   public static void main( String[] Args ) throws Exception    {      g = new DirectedWeightedGraph();	// Create graph.      g.EditGraph();			// Pop open GUI and wait for user.      bellmanford();			// Call function.   }}