[anoneemooz]

Hi I am currently taking up a basic data structures and algorithms course and we're on the topic of Dijkstra's algorithm. Based on sample code online I came up with this:

Dijkstra:

public class Dijkstra 
{

   public static int [] dijkstra ( WeightedGraph wg, int s ) 
   {
      int [] dist = new int [ wg.size() ]; 
      int [] pred = new int [ wg.size() ];
       boolean [] visited = new boolean [ wg.size() ];

      for ( int i = 0 ; i < visited.length ; i++ )
      {
    	  visited[i] = false;
      }
      
      for ( int i = 0 ; i < dist.length ; i++ ) 
      {
    	  dist[i] = Integer.MAX_VALUE;
      }
      
      dist[ s ] = 0;

      for ( int i = 0; i < dist.length ; i++ ) 
      {
		final int next = minVertex ( dist, visited );
		visited[ next ] = true;

		final int [] n = wg.neighbors ( next );
		for ( int j = 0 ; j < n.length ; j++ ) 
		{
			final int v = n[ j ];
			final int d = dist[ next ] + wg.getWeight( next, v );
			if ( dist[ v ] > d ) 
			{
				dist[ v ] = d;
				pred[ v ] = next;
			}
		}
     }
      return pred; 
   }

   private static int minVertex ( int [] dist, boolean [] v ) 
   {
      int x = Integer.MAX_VALUE;
      int y = -1;   // graph not connected, or no unvisited vertices
      for ( int i = 0 ; i < dist.length ; i++ ) 
      {
    	  if ( !v[i] && dist[i] < x )
    	  { 
    		    y = i ;
    		    x = dist[ i ];
    	  }
    	  
      }
      return y;
   }

For your reference here is the WeightedGraph class:

public class WeightedGraph 
{
   private int [][]  paths;  // adjacency matrix
   private Object [] places;

   public WeightedGraph ( int n ) 
   {
      paths  = new int [ n ][ n ];
      places = new Object[ n ];
   }

   public int size() 
   { 
	   return places.length; 
   }

   public void setLabel ( int vertex, Object label ) 
   {
	   places[ vertex ] = label; 
   }
   
   public Object getLabel ( int vertex )              
   {
	   return places[ vertex ]; 
   }

   public void addEdge ( int source, int target, int w )  
   { 
	   paths[ source ][ target ] = w;
   }
   
   public boolean isEdge ( int source, int target )  
   {
	   return paths[ source ][ target ] > 0; 
   }
   
   public void removeEdge ( int source, int target ) 
   { 
	   paths[ source ][ target ] = 0;	
   }
   
   public int getWeight ( int source, int target ) 
   { 
	   return paths[ source ][ target ]; 
   }

   public int [] neighbors ( int vertex ) 
   {
      int count = 0;
      for ( int i = 0 ; i < paths[vertex].length ; i++ ) 
      {
    	  if ( paths[vertex][i] > 0 )
    	  {
    		  count++;
    	  }
      }
      final int [] answer = new int[ count ];
      count = 0;
      for ( int i=0 ; i < paths[ vertex ].length ; i++ ) 
      {
    	  if ( paths[ vertex ][ i ] > 0 ) 
    	 {
    		  answer[ count++ ] = i;
    	 }
      }
      return answer;
   }

   public void print ()
   {
	  	for ( int j = 0 ; j < paths.length ; j++ ) 
	    {
	    	for ( int i = 0 ; i < paths[ j ].length ; i++ ) 
	    	{
	    		if ( paths[ j ][ i ] > 0 ) 
	    		{
	    			System.out.println( places[ j ] + " to " + places[ i ] + " : " + paths[ j ][ i ] + " " );
	    		}
	    	}
	    }
    }
   
   /* This tests WeightedGraph and Dijkstra. Uncomment and  run to try them out and see that they are working fine.
   public static void main (String args[]) 
   {
	      final WeightedGraph t = new WeightedGraph (6);
	      t.setLabel (0, "first");
	      t.setLabel (1, "second");
	      t.setLabel (2, "third");
	      t.setLabel (3, "fourth");
	      t.setLabel (4, "fifth");
	      t.setLabel (5, "sixth");
	      t.addEdge (0,1,2);
	      t.addEdge (0,5,9);
	      t.addEdge (1,2,8);
	      t.addEdge (1,3,15);
	      t.addEdge (1,5,6);
	      t.addEdge (2,3,1);
	      t.addEdge (4,3,3);
	      t.addEdge (4,2,7);
	      t.addEdge (5,4,3);
	      t.print();

	      final int [] pred = Dijkstra.dijkstra (t, 0);
	      for (int n=0; n<6; n++) {
	    	  System.out.print(Dijkstra.printPath (t, pred, 0, n));
	      }
	   }
   */
}

The problem with this though is that it does not work for any source vertex other than 0... it always gives me an arrayindexoutofboundex error : -1 if I try to apply it to another source vertex. What should be added or modified here to allow for any source vertex...

Thanks in advance for all the help and/or direction!

This post has been edited by anoneemooz: 09 October 2010 - 08:26 PM

[macosxnerd101]

Parallel arrays are not a good approach for this. I would suggest incorporating the dijsktra() method as part of the WeightedGraph class so you can directly access the Nodes use them to traverse the Graph in a similar fashion as Trees. It's much cleaner, much better encapsulated, and utilizes standard Graph theory.

[anoneemooz]

macosxnerd101, on 09 October 2010 - 07:29 PM, said:

Parallel arrays are not a good approach for this. I would suggest incorporating the dijsktra() method as part of the WeightedGraph class so you can directly access the Nodes use them to traverse the Graph in a similar fashion as Trees. It's much cleaner, much better encapsulated, and utilizes standard Graph theory.

Thanks for the advice but does that resolve the issue with the code as is? Is it the only way? I'm quite pressed for time since I have to incorporate these into a bigger project due soon and this has been a huge road block for me so I was looking for a way to just make minor edits within the codes as they are to get things working properly. I'll keep your advice in mind for future use though.