Databases
StackOverflow2013
Postsdbo
POPossible free() problem in my Dijkstra algorithm
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POPossible free() problem in my Dijkstra algorithm
    text
    copied!<p>I'm using Dijkstra's to find the shortest path to complete a certain puzzle, where the puzzle works as follows. You have five cyphers, which can be anywhere from -4 to 4 (although they're represented differently, as "very low/high" for -4/4, "low/high" for -3 to -1 or 1 to 3, and "completed" for 0). The objective is to set all five to 0, using the 20 different "techniques" which raise/lower the cypher values by a set amount. If a technique would modify one of the cyphers outside the bounds, i.e above 4 or below -4, then it instead does nothing. So, I've represented it as a graph, where the nodes are all the possible combinations of cypher values, and the starting node is the completed node (0,0,0,0,0). To make it easier, I'm representing the cyphers as values from 0 to 8, with 4 being the completed value - this lets me convert them base 9 into indices of the array of the graph, so there's no time wasted on searches.</p> <p>Now, I've got it all banged out, and I've been debugging and trying to figure out what's wrong, and generally I'll figure a problem out and fix it fine - but this one has me stumped. I'm storing nodes which have a definite distance but which haven't been visited in a linked list, to allow for easy popping of visited nodes. When the linked list gets to 14256 nodes, it fails - but what it fails to do is a free() on the linked list element to be popped. I don't know what could cause a free() to fail and I haven't found anything to help.</p> <p>I haven't asked any questions here before so I don't know the etiquette - I'm going to put the entire source in here because I don't know what is and isn't relevant in this particular situation, but it's about 140 lines which is rather large. On further perusal it appears that there isn't really a tag or anything, so I'll just put it on codepad for now.</p> <p><a href="http://codepad.org/I0K0ETsU" rel="nofollow">http://codepad.org/I0K0ETsU</a></p> <p>Edit: Alright. Okay. Now I've become thoroughly confused. I decided to just comment it out, for giggles - and nothing else goes wrong. It finishes, spits out output.txt, and the text file appears to be perfectly correct. I can't figure out what in the hell is wrong with the code that would make it fall apart on a free() when nothing else is wrong.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload