Kolejka priorytetowa na tablicy.

WItam, jak ustawić kolejkę priorytetową z wierzchołków grafu (reprezentowanych przez obiekt klasy Graph_Node)...

class Graph_node
{
    public:
    
    long int ref; //id wierzcholka
    double lat;
    double lon;

};

... na mapę ....

map <Graph_node*, double> odleglosci;

gdzie jej wartość to odległość tego wierzchołka od źródła (algorytm DIjkstry).

Stwórz tablicę (ja zastąpiłem mapą) d odległości od źródła dla wszystkich wierzchołków grafu. Na początku d[s]=0, zaś d[v]=\infty dla wszystkich pozostałych wierzchołków. 
Utwórz kolejkę priorytetową Q wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego s.

tak aby gdy dam

p.push(Node); //i tak z 10000 tych wierzcholkow, jednoczesnie majac mape z odleglosciami

to gdy wezmę .top() z tej kolejki to zwróci mi node (tzn. element mapy) o najmniejszej odleglosci

Nie da rady, mapa musi mieć unikalny klucz, czyli nie może być dwa węzły z jednakową odległością.

Dzięki za odp. W takim razie o co chodzi w tym algorytmie Dijkstry w podpunkcie 2? Jak ustawić ten priorytet na tę tablicę skoro się nie da?

Mógłbyś to jakoś wytłumaczyć co masz na myśli mówiąc zmienić priorytet?

"Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego s" czyli nie wykluczono że będzie więcej niż jeden węzeł z jednakową odległością od wierzchołka źródłowego s. Mapa nie pozwala mieć dwóch takich samych kluczy. Ale możesz próbować z multimap.
Można też, ba nawet prościej, użyć normalnej kolejki priorytetowej.
Niezależnie od tego co użyjesz podczas działania algorytmu dijkstry może się okazać że musisz dodać węzeł do kolejki, zaś on już tam jest. W tym przypadku nie możesz zmodyfikować jego priorytet czyli odległość, musisz zabrać go z kolejki i wstawić z nowym priorytetem.

Chcesz zrobić dwie sprzeczne ze sobą rzeczy używając tylko jednej podstawowej struktury danych. Tak prosto się tego nie da zrobić. Ja bym rozszerzył tę strukturę, dodając odległość, lub iterator do mapy w danym momencie oraz referencję do obiektu, który reprezentuje node w grafie i dopiero ją umieszczał w mapie odległości -> wskaźnik do tej struktury. W drugim wariancie (z iteratorem) przypisujesz do elementu wskazywanego przez iterator zwrócony w insert ten iterator. Wbudowanej priority_queue nie da się tutaj zastosować, ponieważ nie masz możliwości szybkiego (O(log n)) usunięcia z kolekcji danego elementu, a w mapie możesz znaleźć ten element po iteratorze ponieważ w stercie wskaźniki do elementu się zmieniają podczas operacji na niej, w BST nie (opieram się na tym: http://www.sgi.com/tech/stl/Map.html, jeżeli w standardzie jest inaczej to należy szukać po odległości).

W przypadku użycia tej dodatkowej struktury pamiętaj o przeciążeniu operatora< (lub napisaniu oddzielnej funkcji), jeżeli przy równych odległościach dasz jeszcze porównanie np. wskaźników (bardzo teoretycznie undefined, zawsze można zamiast tego porównywać współrzędne elementów leksykograficznie) to wszystko będzie działało zgodnie z oczekiwaniami. Można też zastosować multimap, ale nie gwarantuje ona wtedy odpowiedniej złożoności pesymistycznej.

Jeżeli nie możesz zmodyfikować tej struktury dodając nowe pole, to mapa nawet nie jest najgłupszym rozwiązaniem. Potrzebujesz jednak posortowanej mapy w drugą stronę, ta pierwsza może być np. hashmapą (w praktyce szybsza niż BST). Jeżeli każdy element ma przypisany sobie unikalny numer porządkowy, to możesz użyć po prostu tablicy jak w oryginalnym pseudokodzie, ale i tak tę drugą mapę potrzebujesz.