Dijkstra's algorithm: segmentation fault

prem · #1 23-Jan-2009, 08:57

hi i ve just implemented dijkstra's algorithm.... used queue... for space constraints i used maps.... but stll getting segmentation fault... can u help

CPP / C++ / C Code:

#include <list>
#include<string.h>
using namespace std;
#include <queue>
  std::queue<int> q; 

# define maxedges 10009
# define maxnodes  10009
# define max 10009
class Graph

{
   private:
  

     struct ListNode

     {

      long long int name;
      long long int pos;
      long long int w;

        struct ListNode *next;      //This creates the same ListNode structure for the next and down pointers each one will have a name, a next, and a down.

        struct ListNode *down;

      };



       ListNode *head;

       ListNode *down_head;



    public:


      Graph() //Constructor

      {

         head = NULL;     //in-line initializations of head and down_head

         down_head = NULL;

      }



         void Build_Network(); //This function will prompt the user for all of the information, as well as perform the necessary linked list operations

         void Display();     
         void display2(long long,long long);     //This function will print out the linked list in a manner that is easily read.



};



#endif //Ends the definition of GRAPH_H



void Graph::Build_Network()

{

   ListNode *newNode;  //This is the new vertex

   ListNode *nodePtr;   //Traversing pointer

   ListNode *downPtr;  //Edge/Adjacent Vertex Traversing pointer


   long long int  num_Nodes,vertex;
   static long long int    i,j,position[100],color[maxnodes],d[maxnodes],count;

   long long int  V_Name[maxnodes],p[maxnodes],t; 
      long long int  E_Name[maxedges+maxedges],v1[maxedges],v2[maxedges];
      static long long  int  state[maxnodes],sum,v,a,b,top,big;
      char str[10];
      



   
       
       //cin>>t;
       scanf("%I64d" ,&t);
       printf("\n");
      while(t)
  //mainwhilet
  {
          
   
    //cin>>num_Nodes;
    scanf("%I64d" ,&num_Nodes);
    long long  int num_Edges;


            
            num_Edges=num_Nodes-1;


     for( i = 0; i<num_Nodes; i++)

    //ifor 
     {

         V_Name[i]=i+1;
         color[i+1]=0;
         d[i+1]=max;
         p[i+1]=0;
         
          
         
      
         
         newNode = new ListNode;

         newNode->name = V_Name[i];



         newNode->next = NULL;

         newNode->down = NULL;

// Building the Vertex List

         if(!head)

            head = newNode;

         else

         {

            nodePtr = head;

            while(nodePtr->next)

            nodePtr = nodePtr->next;

            nodePtr->next = newNode;

           }

}//endifor
           


        for( j=0; j<num_Edges; j++)

      //jfor   
      {
               
        
           
           cin>>v1[j]>>v2[j]>>E_Name[v1[j]+v2[j]+v1[j]*v2[j]];
          // scanf("%I64d %I64d %I64d" ,&v1[j],&v2[j],&E_Name[v1[j]+v2[j]+v1[j]*v2[j]]);
           
            

        
        
        ListNode *nodePtr;
        ListNode *downPtr;
            nodePtr = head;
           
            while(nodePtr)  //continue through all vertices

    {
          vertex=nodePtr->name;
         if(nodePtr->name==v1[j])
         break;
         else
      
          nodePtr=nodePtr->next;
          }
          

            ListNode *downNode;

            down_head =nodePtr->down;

            downNode = new ListNode;
           downNode->name=v2[j];
            downNode->w=E_Name[j];
            downNode->pos=j+1;
            
          
        

            downNode->down = NULL;

            if(!down_head)

            {

               nodePtr->down = downNode;

               down_head = downNode;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode;

            }
        
              
             
  nodePtr = head;
           
            while(nodePtr)  //continue through all vertices

    {
          vertex=nodePtr->name;
         if(nodePtr->name==v2[j])
         break;
          else
          nodePtr=nodePtr->next;
          }

            ListNode *downNode1;

            down_head =nodePtr->down;

            downNode1 = new ListNode;
            
            
          
          
            downNode1->name = v1[j];
            downNode1->w=E_Name[j];
            downNode1->pos=j+1;

            downNode1->down = NULL;



            if(!down_head)

            {

               nodePtr->down = downNode1;

               down_head = downNode1;

            }

            else

            {

               downPtr = down_head;


               while(downPtr->down)

                     downPtr = downPtr->down;


              downPtr->down = downNode1;

            }
         }

      
              
     while(1)
    {              
   //cin>>str;
   scanf("%s",&str);
  while(!q.empty())
  q.pop();
   if(strcmp(str,"DONE")==0)break;
   for(i=0;i<num_Nodes;i++)
   {
                           color[i+1]=0;
         d[i+1]=max;
         p[i+1]=0;
         }
   if(strcmp(str,"CHANGE")==0)
          {
                             // cin>>a>>b;
                             scanf("%I64d %I64d" ,&a,&b);
                             
                              E_Name[v1[a-1]+v2[a-1]+v1[a-1]*v2[a-1]]=b;
                             
          }
   
          if(strcmp(str,"QUERY")==0)
          {
               a=0,b=0;                    
             //cin>>a>>b;
              scanf("%I64d %I64d" ,&a,&b);
             nodePtr = head; 
             color[a]=11;
             d[a]=0;
             p[a]=0;
             q.push(a);
             while(!q.empty())
             {
                              top=q.front();
                            // cout<<"\n topt os "<<top<<"\n";
                              nodePtr=head;
                              while(nodePtr)
                              {
                                   if(nodePtr->name==top)
                                   break;
                                   else         
                                nodePtr=nodePtr->next;            
                              }
                           
                              downPtr=nodePtr->down;
                              while(downPtr)
                              {
                                           vertex= downPtr->name;
                                         //  cout<<"\n adjacent down--vertex"<<downPtr->name;
                                         //  cout<<"\n colrvertex"<<color[vertex];
                                          if(color[vertex]==0)
                                          {
                                          //    cout<<"\ncolr =0";
                                              color[vertex]=11;
                                              p[vertex]=top;
                                             // cout<<"\n d--top"<<d[top];
                                             //  cout<<"\n E--vertex"<<E_Name[vertex+top];
                                              d[vertex]=d[top]+E_Name[vertex+top+vertex*top];
                                              if(d[vertex]>big) big=d[vertex];
                                              q.push(vertex);
                                            
                                           }
                                            
                                            if(vertex==b) 
                                            goto s20;
                                            downPtr= downPtr->down;        
                              }
                              q.pop();
                              color[top]=2;
             }
                              
                              
             
             


                  
                        
                                     
                  

                                  
          
          
        s20:  
                         cout<<d[vertex]<<"\n";
          
          
          } //endif  
          
          }//big while                   
                   
               
t--;
}
}





int main()
{
  
    Graph s;
    s.Build_Network();
 
   
    return 0;
}

and the input output follows the pattern.

Quote:

no.of testcases(bound 10)
no.of nodess (bound 10,000)

node name

no.of adjacent nodes

adjacent node and its weight

no.of paths to find -(bound 100)

source 1 dest 1
.
.
.

plz help

Mexican Bob · #2 24-Jan-2009, 06:01

Since you obviously did not read the guidelines for posting code, go back and read them and then rewrite your post.

Most likely you are chasing an uninitialized pointer or trying to dereference a null pointer.

MxB

prem · #3 25-Jan-2009, 01:46

thanks mexicanBob for reply

Quote:

Originally Posted by Mexican Bob

Since you obviously did not read the www.gidforums.com for posting code, go back and read them and then rewrite your post.

well i ve used code tags and have explained about the prob..the problem must be in linnes of code...but i had to post the entire code cos i am not sure where the error is....but still i ve modidied the graph construction part

Quote:

Most likely you are chasing an uninitialized pointer or trying to dereference a null pointer.

can u elabrate on thsi please.... that ll solve the problem..i am stuck with it for a long long time

more over am not able to edit the first post...the option is disabled.....

prem · #4 25-Jan-2009, 01:58

i have done the following changes in the build function

at the start of build function
i initialised NULL..(first i dint)

CPP / C++ / C Code:

ListNode *newNode = NULL;  //This is the new vertex

   ListNode *nodePtr = NULL;   //Traversing pointer

   ListNode *downPtr = NULL;  //Edge/Adjacent Vertex Traversing pointer[/code]
and i also did downnode->next=NULL in 
[code]while(nodePtr)  //continue through all vertices

    {

         if(nodePtr->name==v1[j])
         break;
          else
          nodePtr=nodePtr->next;
          }

            ListNode *downNode1 = NULL;

            down_head =nodePtr->down;

            downNode1 = new ListNode;

            downNode1->name = v1[j];

            downNode1->down = NULL;
		downNode->next = NULL; //!!!!!!!!!

i will be greatful if u help me with it.
thanks

prem · #5 25-Jan-2009, 10:45

is my way of graph construction and traversals not the ebst ones...its exceeding the time limit....
can i better it anyways...
please help

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
I have a segmentation fault in my project	takachi	C++ Forum	6	09-Mar-2008 22:30
Find the Segmentation Fault	jlwelch	C Programming Language	3	10-Oct-2006 10:16
My Bane - The Segmentation Fault	DCOM	C Programming Language	6	08-Feb-2005 22:58
segmentation fault in c++	rushman8282	C++ Forum	2	26-Jan-2005 03:38
child pid xxx exit signal Segmentation fault (11)	bezak	Apache Web Server Forum	1	24-Nov-2003 09:18

Dijkstra's algorithm: segmentation fault

Re: Dijkstra's algorithm: segmentation fault

Re: Dijkstra's algorithm: segmentation fault

Re: Dijkstra's algorithm: segmentation fault

Re: Dijkstra's algorithm: segmentation fault