C++：オブジェクトへのポインタを持つ優先キューが正しく動作しない

Question

Dijkstra-Algorithmを実装しようとしています。そのために、私はクラス 'Node'のオブジェクトへのポインタを格納する優先度キューを使用しています。これは開始ノードまでの距離が最も短いノードを返します。開始ノードと現在のノードの間の距離を手動で編集し、優先度キューから要素を抽出するようにコードを減らしました。通常、ダイクストラがそれを行います。次のコードは正しく動作しません：

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

をそれが返されます。

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

三回pqが正常に動作しますが、最後にそれは距離2.5で、ノード2を返す必要があります。

どうすればいいですか？答え

Answer 1

あなたがライン以来、そのサイズが縮小されてbeeingてあなたのPRIORITY_QUEUEの要素を飛び出しているのでため

ありがとう：

ノード[2] - >距離= 2.5; ノード[3] - >距離= 3.5;

をに変更する必要があり：

ノード[0] - >距離= 2.5。 ノード[1] - >距離= 3.5;

Answer 2

変数番号nodeNodesは6に等しく設定されます。 main関数の6つのノードを初期化しているため、より小さな数値に減らします。

巨大な数値は、宣言してから何も割り当てなかったため、コンパイラがfloatを初期化するデフォルトのガーベッジです。

この問題を回避するには、変数を使用する前にすべての変数を初期化してください。

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