----------------------------------- Panphobia Wed Mar 05, 2014 8:34 pm Help with algorithm in C ----------------------------------- 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? /*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 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 Sat Mar 08, 2014 6:24 pm Re: Help with algorithm in C ----------------------------------- 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[/code] 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 Sat Mar 08, 2014 10:39 pm Re: Help with algorithm in C ----------------------------------- 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 Sat Mar 08, 2014 10:53 pm Re: Help with algorithm in C ----------------------------------- 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[/code] So the algorithm works for two columns at a time. ----------------------------------- Dreadnought Sat Mar 08, 2014 11:06 pm Re: Help with algorithm in C ----------------------------------- What happens if you don't check the seen array? ----------------------------------- Panphobia Sun Mar 09, 2014 12:46 am RE:Help with algorithm in C ----------------------------------- same thing ----------------------------------- Panphobia Sun Mar 09, 2014 3:47 pm RE:Help with algorithm in C ----------------------------------- 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! ----------------------------------- Dreadnought Sun Mar 09, 2014 3:53 pm Re: Help with algorithm in C ----------------------------------- 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) That's not your compiler, that's the C standard, (look up [url=http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B#Operator_precedence]operator precedence). Did that come up in the snippet you posted? ----------------------------------- Insectoid Sun Mar 09, 2014 3:56 pm RE:Help with algorithm in C ----------------------------------- That's not an issue with the compiler, that's part of the C spec. [url=http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B#Operator_precedence]== takes precedence over &&. In your situation, it evaluates b == b first, which of course is true, so your equation simplifies to a&&c. But yeah, the brackets would have fixed it. EDIT: Damnit, Dreadnaught. ----------------------------------- Panphobia Sun Mar 09, 2014 3:59 pm RE:Help with algorithm in C ----------------------------------- No it was the other way around, a == b && b == c, sorry, as you can see the xEnd = uX && yEnd == uY, so I needed to change it to (xEnd == uX) && (yEnd == uY)