Probleme mit priority_queue Compare Funktion!

Hallo,

Ich arbeite momentan an einer C++ Implementierung des Dijkstra Algorithmus und verwende dazu eine priority_queue.

Die Compare Funktion der queue soll die Nodes absteigend nach der Distanz sortieren (also Knoten mit niedriger Distanz zuerst)

die Knoten Klasse sieht folgendermaßen aus (vereinfacht)

class Node
	{
	private:
		string _name;
		unsigned int _distance;
		Node * _precursor;
		vector<Edge*> _edges;
	public:
		Node();
		Node(string name);

		unsigned int GetDistance() const;
		void SetDistance(unsigned int dist);

		bool less(const Node & other) const
		{
			return ( this->_distance < other.GetDistance() );
		}
		bool operator< (const Node * other) const
		{
			return ( this->_distance < other->GetDistance() );
		}
	};

Die queue erstelle ich folgendermaßen:

priority_queue< Node*, vector<Node*>, std::less<Node*> > pqueue;
		Node * n = start;

		start->SetDistance(0);		// Root Distanz ist 0
		start->SetPrecursor(*start);	// Root Vorgaenger ist Root selbst

		// priority queue fuellen
		for (vector<Node*>::iterator iter = _nodes.begin(); 
			iter != _nodes.end();
			iter++)
		{
			pqueue.push(*iter);
		}

Leider funktioniert die Sortierung (das Einhalten der Prioritäten) aber überhauptnicht.. die queue wird ??irgendwie?? komisch angeordnet.. ich habe keine Ahnung.. sitze nun schon mehrer Stunden und weiß keine Lösung mehr ich habe schon viele andere Comparer probiert aber immer wieder das gleiche seltsame Ergebniss.

Welche Operatoren muss ich überschreiben und was muss ich bei der queue als Comparer Funktion angeben?

bitte um Hilfe, bin verzweifelt

mfg david

CStoll

std::less<Node*> nutzt den op< für zwei Node-Zeiger. Den kannst du nicht überladen (weil nur Build-In's beteiligt sind). Also müsstest du dir einen eigenen Comparator schreiben und mitgeben:

class Node
{
  ... wie bisher
public:
  ...
  //wichtig - der "normale" op< bekommt seinen zweiten Parameter per Referenz
  //dein op< würde einen Node mit einem Node* vergleichen
  bool operator<(const Node& other) const
  { return distance<other.distance; }
};

struct NodePtr_Compare : public binary_function<bool,Node*,Node*>
{
  bool operator()(const Node* l,const Node* r)
  { return *l<*r; }
};

...
priority_queue<Node*,vector<Node*>,NodePtr_Compare> pqueue;
...

(PS: Für später solltest du aus dem NodePtr_Compare ein Template machen und es gut aufheben ;))