c++ - Dijkstra 算法中的优先级队列

Question

这是我的 Dijkstra 算法代码:

#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;
}

在这方面我无法理解

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

这与:

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

这里面的()操作符有什么用？我的意思是它在这段代码中是如何工作的？

另外，为什么我们在 operator() 中使用 &？

此外，这个比较器在优先级队列定义中是如何工作的？为什么我们在运算符定义中使用常量？

我的意思是说这种比较在运算符中究竟是如何工作的，我们不能使用任何其他符号如 = * @ 或任何其他而不是 ()

Answer 1

我认为你写的比较函数是错误的。

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

正确的应该是

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

因为在 priority_queque你会发现表达式 comp(a,b)，其中 comp 是这种类型的对象，a 和 b 是容器中的元素，如果 a 被认为在函数定义的严格弱顺序中先于 b，则应返回 true .

因为在Dijkstra算法中，值越小的节点应该有更高的优先级，所以我们这里使用的运算符应该是

p1.second>p2.second

(通过使用你的代码解决了一个问题，我花了很长时间才弄清楚这个问题，我的程序结果总是与正确的结果不同。)(顺便说一下，在 Dijkstra 算法本身，我认为一旦一个节点作为最小节点弹出，就不需要再次弹出它并更新所有连接到它的节点。这可以节省很多时间。)