C++: Prioritätswarteschlange mit Zeiger auf Objekt funktioniert nicht richtig

Question

Ich versuche, Dijkstra-Algorithmus zu implementieren. Dafür benutze ich eine Prioritätswarteschlange, die Zeiger auf Objekte der Klasse 'Knoten' speichert, die den Knoten mit dem niedrigsten Abstand zum Startknoten zurückgeben sollen. Ich habe meinen Code so reduziert, dass er den Abstand zwischen Startknoten und aktuellem Knoten manuell bearbeitet und Elemente aus der Prioritätswarteschlange extrahiert. Normalerweise würde Dijkstra das tun. Der folgende Code funktioniert nicht richtig:

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(); 
} 

Es gibt:

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

Dreimal die pq richtig funktioniert, aber am Ende sollte es Node 2 mit Abstand 2.5 zurück.

Also wie kann ich es funktionieren lassen?

Danke für Antworten

Answer 1

Da Sie die Elemente Ihrer priority_queue seiner Größe reduziert wird durchgeführt, da die Linie herausspringen werden:

Knoten [2] -> Abstand = 2,5; Knoten [3] -> Abstand = 3,5;

geändert werden soll:

Knoten [0] -> Abstand = 2,5; Knoten [1] -> Abstand = 3,5;

Answer 2

Oben wird die Variable numberNodes gleich 6 gesetzt. Reduziere sie auf eine kleinere Zahl, da sie 6 Knoten in deiner Hauptfunktion initialisiert.

Die große Zahl ist der Standardmüll, zu dem der Compiler den Float initialisiert, seit Sie ihn deklariert haben, ihm aber nichts zugewiesen hat.

Um dieses Problem zu vermeiden, stellen Sie sicher, dass Sie alle Ihre Variablen initialisieren, bevor Sie sie verwenden.