Link to home
Start Free TrialLog in
Avatar of D_basham
D_basham

asked on

If anyone is real familar with dijstra shortest path algorithm please help

Good morning, how are you doing? I was wondering if there is anybody that is really familar with dijstra algorithm could I post my code on it and explain to me why it isn't working. I have looked at this code and the algorithm a 100 times and I don't see why it isn't working. Thanks I will post code when someone responds.
Avatar of baboo_
baboo_

Sure - I am (and I'm sure many others are, too)  Go ahead and post!

baboo_
Avatar of D_basham

ASKER

Thank you so much. I am just not seeing something here. What is happening is the index positions that I want to visit in my distance are working but it is only visting or next is only getting set equal to 0,2,6 of the distance array which obviously are my vertext positions in my graph. I am not visiting 3,4,5? And I can't figure out why. Thank you very much for help.

for(int i=1; i<MAXIMUM; i++)
      {

            distance[i] = INT_MAX;
      }

      distance[start] = 0;

      used_vertex.clear();

      
      occurs = used_vertex.count(next);


      for(allowed_size =1; allowed_size< MAXIMUM; allowed_size++)
      {


      
            for(int j=0; j<MAXIMUM; j++)
            {
                  occurs = used_vertex.count(next);
                  
                  if(occurs == 1)
                  {
                        next++;
                  }
                  
                  else if(distance[j] < distance[j+1])
                  {
                        next = j;
                  
                  }
                  
            }
            
            
            used_vertex.insert(next);

            


            for(v=0; v<MAXIMUM; v++)
            {
                  occurs1 = used_vertex.count(v);

                  if (occurs1  == 0 && edges[next][v] != 0)
                  {
                        
                        sum= distance[next] + (edges[next][v]);
                        
                        if(sum < distance[v])
                        {
                              
                              distance[v] = sum;
                              predecessor[v] = next;
                                                
                        }
                                          
                  }
            
            }
      }
      
Sorry - could you post a bit more of your code?  It'd be helpful to look at what some of these variables and methods are...

baboo_
ASKER CERTIFIED SOLUTION
Avatar of baboo_
baboo_

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Do you mind to post all your code or just important ... and why your program doesn't work ? ==> Any compiling error or just the algorithm gave you the wrong results or it halted during the running time ?
Here are my variables locally in the dijkstra() function. The used_vertex is not my class it is my set. Graph is my class.

I knew there was a problem with my for loop trying to visit all vertexes. I tried a while loop and was not getting that too work at all. When I through in a cout statement to see what vertexes I was setting next to. It was only seeing 0, 2, 6 and skipping 1,3,4,5.
Could I just use a bool variable instead of isDone()? Thanks


int distance[MAXIMUM];
      int predecessor[MAXIMUM];
      set<int> used_vertex;
      int v, allowed_size, sum,next=0,occurs, occurs1, weight,j=0;

CS
Wouldn't this work in the while see if the next is not in the set then keep going? Thanks
      while( used_vertex.count(next) == 0 )
      {
     int dMin = INT_MAX;
     
     for(int j=0; j<MAXIMUM; j++)
     {
          if( used_vertex.count(j) == 0 && distance[j] < dMin )
          {
               dMin = distance[j];
               next = j;
          }
     }

       cout<<next<<"\n";
            used_vertex.insert(next);
I think it is not neccessary ... because next is always in the set when you use 'used_vertex.insert(next)' ... I think the code of baboo is almost correct, just add the 'used_vertex.insert(next)' after the first loop of finding the mininum distance in the non-visited vertexes. To check if all the vertexes have been visited or not you can use 'while (used_vertex.count() == MAXIMUM)' ==> to be sure all vertexes have been visited.
Would parameter would I pass the the count function next?
Maybe the trouble I am having is not setting my predecessor[] to 0 or INT_MAX? Like I am with my distance because when I tried to ouptut the path and I pick like my last value and go to my first value of vertexes it blows up with a run time error. Does that make since to set my predecssesor array to all zero or something is that my issue here is my code to output the path from destination back to source or start:

v=goal;
      
      cout<<distance[goal]<<"\n";
      cout<<goal<<endl;
      while(goal != start)
      {
                  goal = predecessor[goal];
                  cout<<goal<<endl;
      }

Thank you for all your help
This is what I tried and it visted all vertexs but I can't go from my last vertex to my first it blows up. Why is that? Is it this code or how I
Set my predecessor? Thank you all for your help. :)

while( index < MAXIMUM )
      {
     int dMin = INT_MAX;
     
     for(int j=0; j<MAXIMUM; j++)
     {
             used_vertex.insert(next);
         
             if( used_vertex.count(j) == 0 && distance[j] < dMin )
          {
               dMin = distance[j];
               next = j;
          }
     }

       index++;
I know the issue now if I chose a vertex that is anything other then 0 such as 3 then it will keep going up to MAXIMUM and never viste 0,1,or 2. How can I fixe that? Thank you. Based on that while loop?
Thanks everyone I have it now. The insert next into my set was in the wrong place. Sorry okidachi the insert needed to be outside the for loop it was blowing me up inside. Thanks for the help thought.