Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

# Thread: Kindly Help Debug a Dijkstra Algorithm (mostly done, need a nudge)

1. ## 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
{
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);
};```
Based on this, here's what I have for the dijkstra method.
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;
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;
}
}
}```
When I run this, it brings up an error about a vector subscript out of range.

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);`
I found this out by using 2 cout statements, one at the beginning of the first while loop and another between different lines of code all the way down, until I saw one less instance of the second statement. After putting that second statement one line under the specified code, I see it only shows up once (the first statement shows up twice, as did this until then).

So, I've determined where the problem occurs, I just need some help fixing it. Will be greatly appreciated.

2. Have you tried running it through a debugger and step through the process? They have always helped me pin-point errors in scenarios like these.

3. 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.

4. 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.

5. 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.