Help with a little debugging..


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: Help with a little debugging..

  1. #1
    Join Date
    Nov 2003
    Posts
    1

    Help with a little debugging..

    Hi,
    I'm supposed to write the code for Dijkstra's algorithm to work on an adjancy list.
    I have most of it complete, but there is a small bug that I am having difficulty finding.
    For some reason the list is only checking the first three array elements.
    Any help is greatly appreciated.
    Code:
     
    public class dijkstra2 {
     
        // minpath find the lengths of the minimal
        // paths from the first node to every other node
     
        public static int[] minpath(int [] [] [] C){
          int [] D;          // the minimal path lengths
          boolean [] S;      // the set of completed vertices
          int i;
     
          System.out.println("DEBUG: " + C.length + " vertices");
          D = new int[C.length];
          S = new boolean[C.length];
     
         // initialize the set of completed vertices
          S[0] = true;
          for (i = 1; i < C.length; i++) { S[i] = false; }     
     
          // initialize the path lengths
       for(i=0; i<C.length;i++){D[i]=0;}
       for (i=0;i<(C[0]).length; i++) {
         
         D[C[0][i][0]]=C[0][i][1];
         }  
     
    // take one vertex at a time and settle its path length
        for (i = 1; i < C.length; i++) 
      	  {
            int j, k, n, dmin;
            dmin = 0;
            k = -1;
    // choose a vertex k in -S such that D[k] is minimal
            for (j = 1; j < C.length; j++)
            {
              if (!S[j])
              {
                if (!(D[j] == 0))
                {
                  if (dmin == 0 || D[j] < dmin)
                  {
                    dmin = D[j];
                    System.out.println("DEBUG J IS:  "+j);
                    k = j;
                  } 
                }
              }
            }
    	if (k!=-1){S[k]=true;}   
    
    //DEBUG CODE
    System.out.println("DEBUG K IS:  "+k);
    System.out.print("DEBUG:  S IS ");
    for (j=0;j<C.length;j++) {
    System.out.print (" "+S[j]);}
    System.out.println();
    //DEBUG CODE     
    
         	for (j = 1; j < (C[0]).length; j++)
         	{
              if (!S[j])
              {
            	for ( n = 0; n < C[k].length; n++)
            	{
    //D[j] = Math.min(D[j],D[k]+C[k][j]);
      				if (C[k][n][0] == j)
      				{
      					if (D[j]!=0 && D[k]!=0)
      					{  
    						D[j] = Math.min(D[j],D[k]+C[k][n][1]);
     	  					break;
    					}
    				}
        		 }
           	   }
           	  }
    		}     
          return D;
        }
     
    //main program to test the code
        public static void main(String [] args) {
           int ii;
           int [] [] [] AL = { { {1,10},  {2,15},  {3, 5}},
    			   { {0, 7},  {6,32},  {8,16}},
     			   { {0, 2},  {3, 4},  {4, 8},  {8,16}},
    			   { {0, 3},  {2, 5},  {4, 7},  {5, 9},  {7,11}, {8,13}},
    			   { {2, 4},  {3, 6},  {5, 8},  {6,10}},
    			   { {3, 5},  {4, 7},  {7, 9},  {8,11}},
    			   { {1,10},  {4,15},  {7, 5}},
    			   { {3, 1},  {5, 1},  {6, 1}},
    			   { {1, 3},  {4, 3},  {5, 7}} };
           int [] DM;
           DM =  minpath(AL);
           for (ii=0; ii<DM.length; ii++){
           System.out.println("The min dist from node 0 to node "+ii+" is "+DM[ii]);
           }
        }
    }
    Thanks in advance

    [ArchAngel added CODE tags]

  2. #2
    Join Date
    Nov 2003
    Posts
    1

    Smile

    Hi

    A slight question, does your code need to be in a multiple dimensional array? A lot of people try to avoid such complexity.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center