Help with a little debugging..

 DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Help with a little debugging..

1. Registered User
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]);
}
}
}```

2. Registered User
Join Date
Nov 2003
Posts
1
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
•

 FAQ Latest Articles Java .NET XML Database Enterprise