C++の頂点のキュー

Question

私はDijkstraアルゴリズムを実装したいし、キューに頂点を保存する必要があります。

#include <iostream> 
#include <queue> 
using namespace std; 

int main() 
{ 

priority_queue<int> mypq;//I want to put a pointer to vertex instead of int 

mypq.push(10);//Here I want to push vertex 
mypq.push(20); 
mypq.push(15); 

cout << "mypq.top() is now " << mypq.top() << endl; 

return 0; 
} 

コメントセクションをお読みください。

Answer 1

念頭に置いておくべきことは、priority_queueはソートされたコンテナなので、格納されるオブジェクトの比較を定義する必要があります（厳密な弱い順序に従わなければなりません）。

ダイクストラのアルゴリズムについては、各頂点にウェイトがあると仮定し、それらのウェイトで頂点を順序付けしたいとします。

struct vertex { 
    int x, y; 
    unsigned weight; 

    vertex(int x, int y, unsigned weight) : x(x), y(y), weight(weight) {} 
    bool operator <(vertex &other) { return weight < other.weight; } 
}; 

今頂点オブジェクトのPRIORITY_QUEUEは非常に簡単です：

std::priority_queue<vertex> vertices; 

vertices.push(vertex(1, 2, 3)); 
vertices.push(vertex(0, 1, 2)); 
vertices.push(vertex(10, 11, 12)); 

std::cout << "Top = " << vertices.top() << "\n"; 

編集：あなたが動作するようにその最後の行の挿入演算子を定義する必要があります - のようなもの：

std::ostream &operator<<(std::ostream &os, vertex const &v) { 
    return os << "(" << v.x << ", " << v.y << '[' v.weight << "])\n"; 
}