-2

I want to implement Dijkstra algorithm and in serious need for storing vertex in a queue .

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

Read the commented section.

genpfault
  • 51,148
  • 11
  • 85
  • 139
Few Tem
  • 673
  • 1
  • 7
  • 16
  • Are you asking how to create a struct in C++? – pezcode Mar 19 '12 at 17:30
  • 2
    You are in serious need of a C++ book. Have a look at http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list – pmr Mar 19 '12 at 17:32
  • Do you want a queue or a priority queue? Two very different things. A priority queue is not a queue in the normal sense of the word. – Chris Dodd Mar 19 '12 at 17:34

1 Answers1

1

The main thing to keep in mind is that a priority_queue is a sorted container, so it requires that you define a comparison for the objects being stored (which must follow a strict, weak ordering).

Since you talk about Dijkstra's algorithm, let's assume each vertex has a weight, and we want the vertices ordered by those weights.

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

Now a priority_queue of vertex objects is pretty easy:

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: You'll need to define an insertion operator for that last line to work -- something like:

std::ostream &operator<<(std::ostream &os, vertex const &v) { 
    return os << "(" << v.x << ", " << v.y << '[' v.weight << "])\n";
}
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • Thanks for understanding my question and have the time to answer my query . – Few Tem Mar 20 '12 at 04:22
  • I have compiled as you instructed , but I got these errors: http://pastebin.com/raw.php?i=B7vWmqJR :: Also have to mention that it should have been vertices.push ; not vertices.push_back . – Few Tem Mar 20 '12 at 05:53
  • @FewTem: See edited answer (and thanks for the reminder about `push` vs. `push_back` -- sorry 'bout that). – Jerry Coffin Mar 20 '12 at 13:20