bellmanford.java

This is an implementation of bellman ford algorithm using java.

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.
   }
}