Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 5 of 5
  1. #1
    New Coder
    Join Date
    Jan 2013
    Posts
    26
    Thanks
    5
    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);
    };
    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;
    	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;
    	  }
      }
    }
    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.
    Last edited by Reaga; 05-02-2014 at 02:21 AM.

  • #2
    Regular Coder Linux_Sage's Avatar
    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 pin-point errors in scenarios like these.

  • #3
    New Coder
    Join Date
    Jan 2013
    Posts
    26
    Thanks
    5
    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.

  • #4
    New Coder
    Join Date
    Jan 2013
    Posts
    26
    Thanks
    5
    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.

  • #5
    New Coder
    Join Date
    Jan 2013
    Posts
    26
    Thanks
    5
    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.


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •