Kolejka priorytetowa

Witam, napisałem własną implementację Algorytmu Dijkstry która działa elegancko, ale mój "doktor makbuk" oczywiście musiał się czepić że "co z tego że działa jak Alg. Dijkstry" skoro nie ma kolejki priorytetowej i zaczął się bałmuszyć. Ten algorytm działa szybko, jedynie przy znajdywaniu najmniejszego elementu w mapie (map <Wierzcholek*, float>) przelatuje przez wszystkie elementy mapy aby znaleźć Wierzchołek o najmniejszej drodze (float). Myślę czy jakoś nie dałoby się tego zastąpić tą kolejką i byłoby ok.

	//pseudo dijkstra
	void odleglosc_AB(Wierzcholek * A, Wierzcholek * B)
	{		
		map <Wierzcholek*, float> odleglosci; //Wierzcholek, odleglosc od zrodla
		vector <Wierzcholek*> nieprzebadane = this->tablica_wierzcholkow; //tablica wszystkich nieprzebadanych wierzcholkow
		vector <Wierzcholek*> sasiedzi; //sasiedzi wierzcholka
		Wierzcholek * aktualny = A;
		Wierzcholek * koncowy = B;
		long INF = (long)pow(2.0, (8 * sizeof(long int) - 1)); //nieskonczonosc
		int sciezka;
		
		for(int i=0; i<nieprzebadane.size(); i++) //ustawiamy wszystkim nieskonczonosc procz poczatkowego ktoremu droge ustawiamy na 0
		{
			if(nieprzebadane[i] == aktualny) odleglosci[nieprzebadane[i]] = 0;
			else odleglosci[nieprzebadane[i]] = INF;
		}

		while(nieprzebadane.size() > 0 && aktualny != NULL) //dopoki jakis zostal nieprzebadany
		{
			nieprzebadane.erase(nieprzebadane.begin()+znajdz_pozycje(nieprzebadane, aktualny));	//usuwamy go z listy
			
			sasiedzi = this->pobierz_sasiadow(aktualny); //pobieramy sasiadow aktualnego
			
			for(int i=0; i<sasiedzi.size(); i++) //no jak w dijkstrze
			{
				sciezka = odleglosci[aktualny] + this->pobierz_dlugosc_krawedzi(aktualny, sasiedzi[i]);
				if(sciezka < odleglosci[sasiedzi[i]])
					odleglosci[sasiedzi[i]] = sciezka; 
			}
			
			if(nieprzebadane.size() > 0) aktualny = najmniejsza(nieprzebadane, odleglosci); //i tu krzyczal ze funkcja najmniejsza przeszukuje całą tablice (mape) zeby znalesc element najmniejszy w niej wg floata 
			
		}
		
		this->odleglosc = odleglosci[koncowy];
	}

no i ta nieszczesna funkcja

Wierzcholek* najmniejsza(vector <Wierzcholek*> nieprzebadane, map <Wierzcholek*, float> wartosc)
{
	long INF = (long)pow(2.0, (8 * sizeof(long int) - 1));
	float min = wartosc[nieprzebadane[0]];
	Wierzcholek * wierzcholek = nieprzebadane[0];
	
	for(int i=0; i<nieprzebadane.size(); i++)
	{
		if(wartosc[nieprzebadane[i]] < min) { min = wartosc[nieprzebadane[i]]; wierzcholek = nieprzebadane[i]; }
	}
	
	if(min == INF)
		return NULL ;
	else return wierzcholek;
}

Proszę o jakąś pomoc, tu pewnie nie dużo trzeba modyfikować a koleś mnie nieźle wkurzył, całą noc się z tym męczyłem.

Problemem jest ten zapis:
long INF = (long)pow(2.0,8 * sizeof(long int) - 1.0); // od metra operacji na koprocesorze oraz na procesorze wraz z synchronizacją (wykonywane w czasie działania programu),
który w zależności od stanu kontrolnego słowa koprocesora da wynik:
-2147483648
lub:
2147483647
INF=1<<((sizeof(long)<<3)-1); // trzy najszybsze operacje procesora, które wykona kompilator
da wynik: -2147483648
INF=(1<<((sizeof(long)<<3)-1))-1; // cztery najszybsze operacje procesora, które wykona kompilator
da wynik: 2147483647

Zamiast kombinować dziwnie z nieskończonością zrób:

const long int INF = std::numeric_limits<long int>::max();

(Nagłówek <limits>)

Co do kolejki priorytetowej to zapoznaj się z std::priority_queue. To jej gotowa implementacja, musisz tylko ją wykorzystać w Twoim programie. Nie licz, że ktoś zrobi to za Ciebie.

Nigdy na to nie liczyłem! Chciałem jedynie się dowiedzieć w którym miejscu zastąpić kolejką zły fragment. Już chyba wiem. Mam tylko pytanie: jeśli mam kolejkę wskaźników do obiektów klasy Wierzchołek która zawiera pole odleglość (odległość od źródła do tego wierzchołka) to jak zrobić aby priorytet wskazywał właśnie na tę floatową wartość? Przypominam mam kolejkę obiektów a nie floatów

Musisz napisać sobie własny funktor/operator porównujący. Jeżeli chcesz przechowywać wskaźniki nada się tylko funktor. Tutaj masz przykład: http://ideone.com/wNi1r

Ale czy nadal bede mial jakas zlozonosc obliczeniowa jak w kolejce? I jakie parametry przyjmuje poza typem ta kolejka? bo tam są jakieś trzy między < > w tym nazwa chyba klasy