CODEWITHSUNDEEP
c++
Jonathan Chiou
Jonathan Chiou

Reputation: 359

priority queues and dijkstra

Explain to me how to construct a priority queue and why you have to construct that way as though the limit of my my experiences with priority queues is knowing what a queue is (I have never used one in my life).

When I'm looking at this website: http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html

priority_queue<Time, vector<Time>, CompareTime> pq;

I understand that Time is so that you have a queue of Times, Compare Time is what determines the priority of which a time is placed into the queue, but why does vector<Time> need to be in the constructor?

About Dijkstra: I'm implementing a graph as a vector of nodes, which each node containing a list of all its neighbors positions in that vector), so it looks something like this:

class Node {
  protected:
  string name;
  int value;
  list<int> nodes
}

How would I implement this part of Dijkstra:

for each vertex v in Graph:                                
    dist[v] := infinity ;                               
    previous[v] := undefined ;

for dist[v] = infinity, I'm assuming I set the value of every node to infinity, but what variable would allow me to do that? And for previous[v], what does it mean by undefined?

Upvotes: 1

Views: 2865

Answers (2)

Manu343726
Manu343726

Reputation: 14174

Its a programming exercise (Aka you must have to implement everithing), or its a real program?

If is the last, checkout the Standard Library priority queue: http://en.cppreference.com/w/cpp/container/priority_queue

If, on the other hand, its really a learning exercise, after a bit googling you could found this: http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

I could write an introduction/explanation to priority_queues implementation (Max/Min heaps, push/pop operations, etc), but that paper has (I think) really good examples, explanations, and pictures.

EDIT: After seeing your answer to my question "its an exercise or a real program?". I prefer to write the entire answer here, with examples.

STEP1: Setup

std::priority_queue has three template parameters:

  • T: Obviously, the type of the items stored at the container.
  • The underlying container: As its name says, is the type of the underlying container used in the implementation. Its default value is std::vector<T>.
  • Comparer: Functor class that the priority_queue uses to compare items. Its default value is std::less<T> (So, by default, the std::priority_queue is a max priority queue). If you want a min priority queue (As in your case, the Dijkstra's algorithm) you must pass a comparer to do that. Normally, you implement binary operator > for your type, to make std::greater<T> functor work.

STEP2: Using std::priority_queue

So, if you have done the setup fine, you are ready to use std::priority_queue. It has three principal operations:

  • push(): Inserts a value in the piority_queue.
  • pop(): Removes the top of the priority queue.
  • top(): Returns a const reference to the element with maximum (Or minimum, depending on your comparer) priority stored at the priority_queue. Note that top() not remove, it is the work of pop().

Example:

#include <queue>
#include <iostream>

//User defined type. For this short example, a simple uint wrapper:
struct Foo
{
    unsigned int i;

    Foo(unsigned int _i) : i(_i) {}
};

//Implementation of operator> for class Foo, to make std::greater<Foo> work:
bool operator>(const Foo& f1 , const Foo& f2)
{
    return f1.i > f2.i;
}

int main()
{
    std::priority_queue<Foo,std::vector<Foo>,std::greater<Foo>> foo_min_priority_queue;

    foo_min_priority_queue.push(Foo(2));
    foo_min_priority_queue.push(Foo(1));
    foo_min_priority_queue.push(Foo(0));

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 0 
    foo_priority_queue.pop();

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 1 
    foo_min_priority_queue.pop();

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 2 
    foo_min_priority_queue.pop();

    return 0;
}

References:

Upvotes: 3

Nick
Nick

Reputation: 4212

In C++ int max value could be used as infinite

#include <limits>

then use

int imax = std::numeric_limits<int>::max();

Upvotes: 3

Related Questions