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;

< code>()运算符在这里有什么用？我是说它在这段代码中是如何运作的？

还有为什么我们使用

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

我的意思是说运算符中的这种比较到底是如何工作的，我们不能使用任何其他符号作为 = * @ 或任何其他符号来代替（）




Answer 1

声明变量（包括函数参数）时，

至于在这样的结构中使用opera（），它使结构函数的实例成为对象，换句话说，可以像函数一样调用的对象。

Answer 2

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

通过重载 （） 运算符创建函数对象

这作为比较类传递给priority_queue

通过使用此函数对象，队列确定如何插入值（对）。

在这种情况下，pair的第二个值用于比较。

Answer 3

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

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 _ quequeyou中你可以发现表达式comp(a，b)，其中comp是这种类型的对象，a和b是容器中的元素，如果在函数定义的严格弱排序中a被认为在b之前，那么它应该返回true。

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

p1.second>p2.second

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