Hi I have a little problem. I am having a project and i need to implement Dijkstra for a graph.So far it was ok but i have that problem when run it in g++
The code is where i think i have the error is here i think:

if(!graph_list.at(start_Node->id)->path_list.empty())
            {
                vector<Edge>::iterator it=graph_list.at(start_Node->id)->path_list.begin();
                for(;it!=graph_list.at(start_Node->id)->path_list.end();it++)
                {
                    if(graph_list.at(it->destination_Node->id)->colour==WHITE)
                    {
                        next_Node=it->destination_Node;
                        next_Node->cost+=it->distance;
                        graph_list.at(next_Node->id)->colour=GREY;
                        pri_queue.push(next_Node);
                    }

                    //relax the cost
                    if(graph_list.at(it->destination_Node->id)->cost>
                       graph_list.at(start_Node->id)->cost+it->distance)
                       {
                           graph_list.at(it->destination_Node->id)->cost=
                           graph_list.at(start_Node->id)->cost+it->distance;
                           graph_list.at(it->destination_Node->id)->previous=start_Node;
                       }
                }

And the error is :

/share/gcc/el6-x86_64/gcc-4.8.1/include/c++/4.8.1/bits/stl_heap.h:218:
    error: elements in iterator range [__first, __last - 1) do not form a     
    heap with respect to the predicate __comp.

Objects involved in the operation:
iterator "__first" @ 0x0x7fff29ee4680 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPPN13Datastructure4NodeENSt9__cxx19986vectorIS5_SaIS5_EEEEENSt7__debug6vectorIS5_S9_EEEE (mutable iterator);
  state = dereferenceable (start-of-sequence);
  references sequence with type `NSt7__debug6vectorIPN13Datastructure4NodeESaIS3_EEE' @ 0x0x7fff29ee4680
}
iterator "__last - 1" @ 0x0x7fff29ee4340 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPPN13Datastructure4NodeENSt9__cxx19986vectorIS5_SaIS5_EEEEENSt7__debug6vectorIS5_S9_EEEE (mutable iterator);
  state = dereferenceable;
  references sequence with type `NSt7__debug6vectorIPN13Datastructure4NodeESaIS3_EEE' @ 0x0x7fff29ee4340

Can anybody help me where is the problem ?
Thank you in advance

Edited 2 Years Ago by spawn2004

After a little changes in my function now it looks like that

priority_queue<Node*,vector<Node*>,Compare> pri_queue;
Node* start_Node;

reset_Node();

//start with the source node
graph_list.at(from)->cost=0;
graph_list.at(from)->colour=GREY;
pri_queue.push(graph_list.at(from));//push the source into the priority queue

while(!pri_queue.empty())
{
  start_Node=pri_queue.top();//take the top Node from the queue
  pri_queue.pop();//remove  the top element for the queue

  if(start_Node->id==to)
  {
     vector<unsigned int> temp_ids;
     unsigned int temp=graph_list.at(to)->previous->id;

     while(temp!=from)
     {
       temp_ids.push_back(temp);
       temp=graph_list.at(temp)->previous->id;
     }

     cout<<MSG_ROUTE;
     cout<<from<<SEPARATOR<<graph_list.at(from)->name<<endl;
     vector<unsigned int>::reverse_iterator rev_it;
     for(rev_it=temp_ids.rbegin();rev_it!=temp_ids.rend();++rev_it)
     {
       cout<<*rev_it<<SEPARATOR<<graph_list.at(*rev_it)->name<<endl;
     }
     cout<<to<<SEPARATOR<<graph_list.at(to)->name<<endl;
     return true;
  }

  if(!start_Node->path_list.empty())
  {
    vector<Edge>::iterator it=start_Node->path_list.begin();
    for(;it!=start_Node->path_list.end();++it)
    {
      if(it->destination_Node->colour==WHITE)
      {
        it->destination_Node->colour=GREY;
        pri_queue.push(it->destination_Node);
      }

     //relax the Node
      if(it->destination_Node->cost>start_Node->cost+it->distance)
      {
       it->destination_Node->cost=start_Node->cost+it->distance;
       it->destination_Node->previous=start_Node;
     }
   }
 }
 start_Node->colour=BLACK;
}

but it is strange that only when i call that function i have that problem:

/share/gcc/el6-x86_64/gcc-4.8.1/include/c++/4.8.1/bits/stl_heap.h:218:
    error: elements in iterator range [__first, __last - 1) do not form a     
    heap with respect to the predicate __comp.

Objects involved in the operation:
iterator "__first" @ 0x0x7fff67761db0 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPPN13Datastructure4NodeENSt9__cxx19986vectorIS5_SaIS5_EEEEENSt7__debug6vectorIS5_S9_EEEE (mutable iterator);
  state = dereferenceable (start-of-sequence);
  references sequence with type `NSt7__debug6vectorIPN13Datastructure4NodeESaIS3_EEE' @ 0x0x7fff67761db0
}
iterator "__last - 1" @ 0x0x7fff67761a70 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPPN13Datastructure4NodeENSt9__cxx19986vectorIS5_SaIS5_EEEEENSt7__debug6vectorIS5_S9_EEEE (mutable iterator);
  state = dereferenceable;
  references sequence with type `NSt7__debug6vectorIPN13Datastructure4NodeESaIS3_EEE' @ 0x0x7fff67761a70
}

Knowing how the Dijkstra algorithm operates, I would assume that your "Compare" function relies on a "distance" values associated to the nodes, and that these distance values change during the iterations of the algorithm. As the distance values change, the priority-queue (which is just a "heap") becomes corrupt, or out of order (i.e., the "heap-property" no longer holds true). This is why the error occurs. You simply cannot change the distance value without updating the priority-queue to make sure that it remains valid. You need to use a kind of heap or priority-queue that can be updated on-the-fly. The standard priority-queue does not allow that. Find another one, or implement your own (personally, I use the boost::d_ary_heap_indirect class, but it's a little hard to use).

played by a user versus the computer.
Computer moves should be identical to those of the human user’s moves but of course produced using a random pattern.

Opening Screen
The program should display a menu from which you chose to play or quit.
Display before the menu the name of the game and let it blink for few seconds.
After the end of each game you need to clear the screen and redisplay the menu.

The Game
Your game is a simulation of tossing a coin and it is formed of five turns for each player (a total of 10 turns).
You start with the human player than the computer player .
At the end of the gem, your program must indicate who the winner is.
In a turn, the program asks the player how many times he wants to toss the three coins together. For example,
In Turn 1 a player may chose to toss the coin twice while in turn 2 he may chose to toss the coin five times.
When the three coins are tossed and the player gets two heads and a tail this should be marked as a successful trial.
By the end of a player’s turn, if he had a successful trial count greater than half his chosen trial number then he
scores 1 point out of 5.
When it is the computer’s turn, let the program print out messages to indicate what the computer is doing.

You must have a least two functions. Make sure to use call-by-reference in one of those functions and also make sure that at least one of them returns back a value to main. Your functions should contain at least 5 lines of code.
You are not allowed to use global variables.

Comments
Create a new thread please
This question has already been answered. Start a new discussion instead.