Очередь вершин в C ++

Question

Я хочу реализовать алгоритм Дейкстры и остро нуждаюсь в хранении вершин в очереди.

#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; }
};

Теперь очередь приоритетов для объектов вершин довольно проста:

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";

Edit: вам нужно определить оператор вставки для этой последней строки для работы - что-то вроде:

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