Help with algorithm in C

[Panphobia]

So I am using ncurses so that is probably why some of the functions will be strange. But basically I am trying to find the shortest path from one point to another on the terminal, and keep track of the path, so I used Dijkstra. Sufficed to say, it isn't working, I checked my code for the queue, and it works perfectly, so I can only think that there is a problem in the logic. But the problem there is that I translated the code to java and it worked perfectly there. So here is my code, can anyone see the problem?

c:

/*while there are elements in the q*/     /*struct and pointer are passed*/     while(dq(qY,&uY)!=0 && dq(qX,&uX)!=0)     {         /*break if at the end*/         if(uX == xEnd && uY == yEnd)         {             break;         }                 /*Neighbours around the current cell*/         for(i=0;i<4;++i)         {                         vX = uX + neighbours[i][0];             vY = uY + neighbours[i][1];                         /*If the new cell is out of bounds continue*/             if(vY<0||vX<0||vY>70-1||vX>150-1)             {                 continue;             }             c = (char)mvinch(vY,vX);                         /*If the new cell is over a cell which is a boundary continue*/             if(c=='|'||c=='-'||c=='.'||c=='+')             {                 continue;             }                         alt = p->minPath[uY][uX]+1;                         if(alt < p->minPath[vY][vX])             {                 p->minPath[vY][vX]=alt;                 p->prev[vY][vX][1]=uX;                 p->prev[vY][vX][0]=uY;                                 /*enqueue*/                 eq(qX,vX);                 eq(qY,vY);             }         }     }

[Dreadnought]

Panphobia wrote:

Sufficed to say, it isn't working

It might be useful to know how it isn't working?

Here's the only "potential problem" I noticed, but its probably nothing.

There is an inconsistency in the way you store (x, y) coordinates

c:

vX = uX + neighbours[i][0]; vY = uY + neighbours[i][1];

c:

p->prev[vY][vX][1]=uX; p->prev[vY][vX][0]=uY;

Not necessarily an issue, but it might be the cause of some weird behavior. Personally, I would use a struct or at least preprocessor symbols. (#define)


On a different note, since the distance between neighboring nodes is always 1, any node you have already visited must have been visited by a shortest path.
This means that you could save some time by doing this. (and only have to calculate the length of the path at the end)

c:

/*Neighbours around the current cell*/ for(i=0;i<4;++i) {     vX = uX + neighbours[i][0];     vY = uY + neighbours[i][1];     if (visited[vX][vY])         continue;     // ...

As I said not much but maybe this will help.
Good luck!

[Panphobia]

Yea I have used the seen int/bool array, it didn't do anything but improve the space complexity. Also they aren't (x,y), in ncurses when you're looking on the screen, you have to search (y,x). Well when I say it isn't working, I say it is breaking after one round of en queuing and then dequeuing, so basically if this was the minpath array initialization
I = INFINITY

code:

I I I I I I I I I I I I I I I I

it only does this

code:

0 1 I I 1 I I I I I I I I I I I

[Dreadnought]

Quote:

Also they aren't (x,y), in ncurses when you're looking on the screen, you have to search (y,x).

My point was that in one instance index 0 is X and index 1 is Y and in the second instance it is reversed, but that shouldn't cause a problem.

Quote:

Yea I have used the seen int/bool array, it didn't do anything but improve the space complexity.

Ya, it doesn't improve complexity, but it seems weird that you check the length of the path each time you look at a vertex except for the last vertex (where you break on the iteration after you reach it). But honestly that's just me quibbling about consistency.

Also, shouldn't you initialize to this?

code:

0 I I I I I I I I I I I I I I I

I don't know what infinity + 1 will do, but it might be interesting.

Other than that I'm stumped, maybe if you can provide more details of the behavior (does it crash after the first enqueue/dequeue, or does it exit the while loop?), but otherwise I have no idea.

Sorry,

[Panphobia]

By the way, I know what you're saying, and it first gets initialized to all infinity, but the start node gets set to 0 right before the while loop. Also the neighbors array where I switched it doesn't matter as you said, soooooo, this is bugging me. It doesn't make sense because the same code in Java works PERFECTLY.

[Dreadnought]

Well, it shouldn't be too hard to figure out where the problem occurs since its after the first enqueue/dequeue.
Put some debug prints in (even better, use a debugger) and figure out where stuff goes wrong.

It might not be fun, but debugging is at least half the work (usually much more than half )

[Panphobia]

Yea I know debugging is a big part of coding. I think I got one bug, and a few others. I forgot to malloc the variables in the struct, and also I changed the queue so that it takes in 1D arrays instead of ints. But the algorithm works until the distance from the origin is more than 10, then it breaks down. Like for the distance from (0,0) to (10,10) it printed 414, but when it is (0,0) to (1,1) it says the distance is 2, it doesn't make sense. Here is the revised code, and I put the "isVisited" variable in this time.

c:

p->minPath[yStart][xStart]=0;     u[0]=yStart;     u[1]=xStart;     eq(q,u);         /*while there are elements in the q*/     while(dq(q,&u))     {                 uX = u[1];         uY = u[0];         /*break if at the end*/         if(uX == xEnd && uY == yEnd)         {             break;         }         seen[uY][uX]=1;                 /*Neighbours around the current cell*/         for(i=0;i<4;++i)         {                         vX = uX + neighbours[i][1];             vY = uY + neighbours[i][0];             /*If the new cell is out of bounds continue*/             if(vY>=0&&vX>=0&&vY<=70-1&&vX<=150-1&&seen[vY][vX]==0)             {                 c = (char)mvinch(vY,vX);                             /*If the new cell is over a cell which is a boundary continue*/                 if(c!='|'&&c!='-'&&c!='.'&&c!='+')                 {                     alt = p->minPath[uY][uX]+1;                                   if(alt < p->minPath[vY][vX])                     {                         p->minPath[vY][vX]=alt;                         p->prev[vY][vX][1]=uX;                         p->prev[vY][vX][0]=uY;                                                 u[0]=vY;                         u[1]=vX;                                                 /*enqueue*/                         eq(q,u);                     }                 }             }         }     }

[Dreadnought]

Welp, in my boredom I coded your algorithm (in Turing ), as far as I know, it works.

If you ask me the problem probably lies in the queue or in p (whatever kind of structure it is), unless I'm missing something.

When you say things break when you hit (0,0) to (10,10).
what happens for (0,0) to (9,9), (9, 10), (10,9) (9, 11), (11, 9) and basically any nearby case?

Good luck.

[Panphobia]

The same thing happens for those too, I think it happens when the distance from (0,0) is > 10. I tested my queue A LOT and I know it is not the problem, I even went to my professor and she said it was fine. My structure just holds the minpath,and the prev array.

[Panphobia]

Let me show you the results of a 20 by 20 grid without any walls, this is just a pure shortest path to any point on a 20 by 20 grid.

code:

@    1    140  141  142  143  282  283  284  285  424  425  426  427  566  567  568  569  708  709 1    2    139  140  143  144  281  282  285  286  423  424  427  428  565  566  569  570  707  708 2    3    138  139  144  145  280  281  286  287  422  423  428  429  564  565  570  571  706  707 3    4    137  138  145  146  279  280  287  288  421  422  429  430  563  564  571  572  705  706 4    5    136  137  146  147  278  279  288  289  420  421  430  431  562  563  572  573  704  705 5    6    135  136  147  148  277  278  289  290  419  420  431  432  561  562  573  574  703  704 6    7    134  135  148  149  276  277  290  291  418  419  432  433  560  561  574  575  702  703 7    8    133  134  149  150  275  276  291  292  417  418  433  434  559  560  575  576  701  702 8    9    132  133  150  151  274  275  292  293  416  417  434  435  558  559  576  577  700  701 9    10   131  132  151  152  273  274  293  294  415  416  435  436  557  558  577  578  699  700 10   11   130  131  152  153  272  273  294  295  414  415  436  437  556  557  578  579  698  699 11   12   129  130  153  154  271  272  295  296  413  414  437  438  555  556  579  580  697  698 12   13   128  129  154  155  270  271  296  297  412  413  438  439  554  555  580  581  696  697 13   14   127  128  155  156  269  270  297  298  411  412  439  440  553  554  581  582  695  696 14   15   126  127  156  157  268  269  298  299  410  411  440  441  552  553  582  583  694  695 15   16   125  126  157  158  267  268  299  300  409  410  441  442  551  552  583  584  693  694 16   17   124  125  158  159  266  267  300  301  408  409  442  443  550  551  584  585  692  693 17   18   123  124  159  160  265  266  301  302  407  408  443  444  549  550  585  586  691  692 18   19   122  123  160  161  264  265  302  303  406  407  444  445  548  549  586  587  690  691 19   20   121  122  161  162  263  264  303  304  405  406  445  446  547  548  587  588  689  690

As you can see, there is an actual problem, and I don't know what it is. The shortest path is accurate for the two leftmost columns, but that is it.

[Dreadnought]

Things I might try if I were debugging this:

1- What do p->prev tell you the shortest path is? (does it even make sense?)
2- What happens if you remove the seen array? (do the minpath values change? If they do you might be able to get an idea of what's happening)
3- What happens when you give it a 20x1 grid? (since things seem to go wrong in the horizontal direction)
4- (Probably one of the first things I would have tried, lots of prints (and if they don't tell me anything interesting, I put more!)

You might have already tried some of these. I'm assuming you've tried 4 to some extent, but you should consider putting A LOT of prints and writing everything to a file.
Then you can look through it and check what happens at important moments (like when you suddenly jump from 1 to 140 and stuff.

Again, if I had to guess, I'd say something bad is happening in p.

Good luck.

[Panphobia]

If I reduce the rows and the columns to 10 this is the output

code:

0    1    20   21   22   23   42   43   44   45 1    2    19   20   23   24   41   42   45   46 2    3    18   19   24   25   40   41   46   47 3    4    17   18   25   26   39   40   47   48 4    5    16   17   26   27   38   39   48   49 5    6    15   16   27   28   37   38   49   50 6    7    14   15   28   29   36   37   50   51 7    8    13   14   29   30   35   36   51   52 8    9    12   13   30   31   34   35   52   53 9    10   11   12   31   32   33   34   53   54

So the algorithm works for two columns at a time.

[Dreadnought]

What happens if you don't check the seen array?

[Panphobia]

same thing

[Panphobia]

I figured it out, the C compiler I am using is weird, when building a propositional statement like a&&b == b && c you need brackets, (a && b) == (b && c), also I wasn't checking whether the index of the prev array was filled, so there were my problems. Thanks for the help!