2 Replies - 11175 Views - Last Post: 09 October 2010 - 08:37 PM Rate Topic: -----

#1 anoneemooz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 09-October 10

Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

Posted 09 October 2010 - 08:05 PM

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


Is This A Good Question/Topic? 0
  • +

Replies To: Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10809
  • View blog
  • Posts: 40,290
  • Joined: 27-December 08

Re: Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

Posted 09 October 2010 - 08:29 PM

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.
Was This Post Helpful? 0
  • +
  • -

#3 anoneemooz  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 09-October 10

Re: Dijkstra's Algorithm: Java Implementation Source Vertex Issues...

Posted 09 October 2010 - 08:37 PM

View Postmacosxnerd101, 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1