Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 5 of 5

05022014, 02:15 AM #1
 Join Date
 Jan 2013
 Posts
 31
 Thanks
 8
 Thanked 0 Times in 0 Posts
Kindly Help Debug a Dijkstra Algorithm (mostly done, need a nudge)
Optional hw assignment. Graph defined by a text file, dijkstra method to run through the graph with a starting vertex number.
We're only allowed to change the dijkstra method, everything else must remain as the professor programmed.
The idea is that we run from the command line like so: programName textFile x, where x is the starting vertex.
Graph definition in a header file:
Code:class Graph { struct Edge { int dest; // destination vertex number int cost; // edge weight Edge *next; }; struct Vertex { Edge *adj; bool known; int dist; int path; }; vector<Vertex *> vertices; vector<int> PQ; //priority queue int PQsize; void PQinsert (int v); //glorified enqueue int PQdeleteMin (); //glorified dequeue public: Graph () { PQsize=0; } int numVertices () { return vertices.size(); } int dist (int dest) { return vertices[dest]>dist; } void readFile (char *name); //creates the graph from file void dijkstra (int start); //the only method I'm allowed to write myself void printPath (int dest); };
Code:void Graph::dijkstra (int start) { Vertex *startV = vertices[start]; startV>path = INFINITY; for (int i=start; i < this>numVertices(); i++) { vertices[i]>dist = INFINITY; //in the header, INFINITY is defined as INT_MAX vertices[i]>known = false; } startV>dist = 0; PQinsert(start); while(PQ.size() > 0) { Vertex *v = vertices[this>PQdeleteMin()]; v>known = true; Edge *e = v>adj; while (e!=NULL) { Vertex *w = vertices[e>dest]; if(w>known==false) { int cvw = e>cost; if(v>dist + cvw < w>dist) { w>dist = v>dist + cvw; w>path = v>path; PQinsert(w>path); } } e = e>next; } } }
Through a series of cout statements to determine how far it gets, I've determined that it runs through all loops at least once, but brings up that error at the second attempt to run this line:
Code:PQinsert(w>path);
So, I've determined where the problem occurs, I just need some help fixing it. Will be greatly appreciated.Last edited by Reaga; 05022014 at 02:21 AM.

05022014, 03:21 AM #2
 Join Date
 Mar 2014
 Location
 Sterling,VA
 Posts
 106
 Thanks
 0
 Thanked 10 Times in 10 Posts
Have you tried running it through a debugger and step through the process? They have always helped me pinpoint errors in scenarios like these.

05022014, 03:43 AM #3
 Join Date
 Jan 2013
 Posts
 31
 Thanks
 8
 Thanked 0 Times in 0 Posts
I'm afraid not, I'm not entirely certain how to use a Debugger, haven't been taught that. I try the one with Visual Studio 2012 and it brings me to a line in stdthrow.cpp, which I'm fairly certain won't give me any insight.

05022014, 04:35 AM #4
 Join Date
 Jan 2013
 Posts
 31
 Thanks
 8
 Thanked 0 Times in 0 Posts
Apparently that error about the "vector subscript out of range" is an Assertion Failure. I don't know if that's helpful, but there's a little extra info.

05022014, 04:54 AM #5
 Join Date
 Jan 2013
 Posts
 31
 Thanks
 8
 Thanked 0 Times in 0 Posts
Oh well, it's an optional assignment for extra credit I'm not certain I need (he hasn't given back a grade on the last 2 assignments yet) and I'm about out of time now. So, if a mod or whatever would close this, that'd be nice.