Priority queue in Dijkstra's algorithm

Question

This is my code for Dijkstra's algorithm:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>

#define pp pair<int,int>
using namespace std;
struct pri
{
    int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
    {
        return p1.second<p2.second;
    }
}p;
int main()
{
    priority_queue<pp,vector<pp>,pri> q;
    int n;
    cin>>n;
    vector<pp> g[n+1];
    int e,u,v,w,i;
    cin>>e;
    for(i=0;i<e;i++)
    {
        cin>>u>>v>>w;
        g[u].push_back(pp(v,w));
        g[v].push_back(pp(u,w));
    }
    int s;
    cin>>s;
    int d[n+1];
    for(i=1;i<=n;i++)
        d[i]=999;
    d[s]=0;
    q.push(pp(s,d[s]));
    while(!q.empty())
    {
        u=q.top().first;
        q.pop();
        int size=g[u].size();
        for(int i=0;i<size;i++)
        {
            v=g[u][i].first;
            w=g[u][i].second;
            cout<<u<<" "<<" "<<w<<endl;
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push(pp(v,d[v]));
            }
        }
    }
    for(i=1;i<=n;i++)
        printf("node %d,min weight=%d\n",i,d[i]);
    return 0;
}

In this I can't understand the working of

 priority_queue<pp,vector<pp>,pri> q;

That is related to:

struct pri
{
    int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
    {
        return p1.second<p2.second;
    }
}p;

What is the use of () operator in this? I mean how it functions in this code?

Also why are we using & in operator()?

Also, how does this comparator work in priority queue definition? And why are we using constant in operator definition?

i mean to say how is exactly this comparison in operator working and cant we use any other symbol as = * @ or any other instead of ()

Answer 1

I think the compare function you write is wrong.

int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
{
    return p1.second<p2.second;
}

which the correct one should be

int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
{
    return p1.second>p2.second;
}

Because in priority_quequeyou can find that The expression comp(a,b), where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.

Because in the Dijkstra algorithm, the node with smaller value should has higher priority, thus the operator we used here should be

p1.second>p2.second

(By using your code to solve a problem, it took me a long time to figure out this problem that my program's results were always different with the correct one.) (By the way, in the Dijkstra algorithm itself, I think once a node was pop as the smallest one, there is no need to pop it again and update all the nodes that connected to it. This could save a lot of time.)