在Dijkstra算法优先级队列 [英] Priority queue in Dijkstra's algorithm

问题描述

这是我的$ C $下Dijkstra算法：

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

在此我无法理解的工作

 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怎样的功能呢？

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 ()

推荐答案

我觉得你写的比较功能是错误的。

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

由于在 priority_queque 你可以发现，前pression补偿（ A，B），其中补偿就是这种类型，a和b的对象是在容器中的元素，如果被认为是B前面走在严格的弱序化的函数定义应返回true。

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.

由于在Dijkstra算法，具有较小值的节点应该具有更高的优先级，因此，我们这里使用的操作者应

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

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

(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.)

这篇关于在Dijkstra算法优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！