CODEWITHSUNDEEP
c++ooppointersstl
robert_2486
robert_2486

Reputation: 1

C++: priority queue with pointer to object does not work correctly

I am trying to implement Dijkstra-Algorithm. For that i am using a priority queue storing pointers to objects of the class 'Node' which shall return the node with the lowest distance to the start node. I reduced my code so that it manually edits the distance between start node and current node and extracts element from the priority queue. Normally Dijkstra would do that. The following code does not work correctly:

using namespace std;

#include <iostream>
#include <limits>
#include <vector>
#include <queue>

const int numberNodes = 6;
int IMAX = numeric_limits<int>::max();

class Node{
public:
    Node(float pdistance, int pid){distance = pdistance;    id = pid;}
    float distance;
    int id;     //only for debug
};

Node** nodes;       //in int main() Array of Node*

class Compare{  //Compare pointer to nodes based on distance to start node (Dijkstra)
public:
    bool operator() (Node *n1, Node *n2) const {
        return n1->distance>n2->distance;
    }
};

priority_queue<Node*, vector<Node*>, Compare> pq;

int main(){
    nodes = new Node*[numberNodes];
    for(int i=0; i<numberNodes; i++){       //create new objects and store them in pq
        nodes[i] = new Node(IMAX, i);
        pq.push(nodes[i]);
    }
    Node* sNode;        //Start node. not contained in nodes[]
    sNode = new Node(0, -1);        //distance 0, id -1
    pq.push(sNode);

    cout << "extracted: Node " << (pq.top())->id << " , distance " << (pq.top())->distance << endl;
    pq.pop();

    nodes[0]->distance = 0.5;
    nodes[1]->distance = 0.5;
    cout << "extracted: Node " << (pq.top())->id << " , distance " << (pq.top())->distance << endl;
    pq.pop();       

    cout << "extracted: Node " << (pq.top())->id << " , distance " << (pq.top())->distance << endl;
    pq.pop();   

    nodes[2]->distance = 2.5;
    nodes[3]->distance = 3.5;
    cout << "extracted: Node " << (pq.top())->id << " , distance " << (pq.top())->distance << endl;
    pq.pop();   
}

It returns:

extracted: Node -1 , distance 0
extracted: Node 0 , distance 0.5
extracted: Node 1 , distance 0.5
extracted: Node 5 , distance 2.14748e+09

Three times the pq works correctly, but at the end it should return Node 2 with distance 2.5.

So how can i make it work?

Thanks for answers

Upvotes: 0

Views: 681

Answers (2)

Viliami
Viliami

Reputation: 628

At the top the variable numberNodes is set equal to 6. Reduce it to a smaller number since it is initializing 6 nodes in your main function.

The huge number is the default garbage that the compiler will initialize the float to since you declared it but didn't assign anything to it.

To avoid this problem just make sure that you initialize all your variables before you use them.

for(int i=0; i<numberNodes; i++){       //create new objects and store them in pq
    nodes[i] = new Node(IMAX, i);
    nodes[i].distance = 0.0f; //<--set a default value
    pq.push(nodes[i]);
}

Upvotes: 0

P. Pazzini
P. Pazzini

Reputation: 11

Since you are popping out the elements of your priority_queue its size is beeing reduced, since the line:

nodes[2]->distance = 2.5; nodes[3]->distance = 3.5;

Should be changed to:

nodes[0]->distance = 2.5; nodes[1]->distance = 3.5;

Upvotes: 1

Related Questions