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()中使用&？

还有，这个比较器在优先队列定义中是如何工作的？为什么在操作符定义中要使用常数？

我的意思是说，这个操作符中的比较是如何工作的？我们不能使用其他符号，比如= * @或任何其他符号来代替()吗？

- ayush nigam

---

请适当缩进。 - Maxime Chéramy

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

因为在优先队列中，您可以发现表达式comp(a,b)，其中comp是此类型的对象，a和b是容器中的元素，如果在函数定义的严格弱序中认为a排在b之前，则应返回true。

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

p1.second>p2.second

使用您的代码解决问题时，我花了很长时间才发现我的程序结果总是与正确的结果不同。

顺便说一句，在Dijkstra算法本身中，我认为一旦将一个节点作为最小节点弹出，就没有必要再次弹出它并更新所有与其相连的节点。这可以节省很多时间。

- Fmars

Answer 2

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

通过重载()运算符创建函数对象，并将其作为比较类传递给优先队列。

使用&将pair作为常量引用传递，确保不会复制实际参数（通过引用传递它们），同时该函数无法修改它们的值（使用const关键字）。

通过使用此函数对象，队列确定如何插入值（pair）。在这种情况下，使用pair的第二个值进行比较。

- P0W

Answer 3

我觉得你的问题是关于这行代码：priority_queue<pp,vector<pp>,pri> q;？

这个声明了一个类型为priority_queue<pp,vector<pp>,pri>的变量q。 priority_queue被定义为

template<class T,
         class Container = vector<T>,
         class Compare = less<typename Container::value_type> >
class priority_queue;

所以，pp 是元素的类型，vector<pp> 是容器（与默认值相同），pri 是用于比较队列中项目的函数对象（Compare）。priority_queue 使用 Compare 来排序其元素。如果元素不能直接进行比较，或者默认值不合适，则可以提供自己的比较方式。在这种情况下，元素将按照每个元素 pair 中的 second 成员顺序排列。

- cdmh

---

这是一个实现了公共operator()()的struct或class，因此该类的实例可以像函数一样使用。请参见http://www.cprogramming.com/tutorial/functors-function-objects-in-c++.html。 - cdmh

Answer 4

在声明变量（包括函数参数）时，&用来标记变量作为引用。对于某些类型的参数使用引用是非常基本和常见的事情，部分原因是它可以传递参数而不创建副本（如对于 std::vector 很有效），还允许非 const 引用作为输出参数在函数中进行更改。

至于在此类结构中使用 operator()，它使结构的实例成为function objects，换句话说，可以像函数一样调用的对象。

- Some programmer dude

Answer 5

我重构了这段代码，并在hackerrank上进行了检查。

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <iterator>
#include <algorithm>
#include <functional>

using namespace std;

struct pri
{
    typedef pair<int,int> pp;
    typedef deque<pri::pp > list;
    typedef vector< pri::list > graph;
    int operator() (pp&p1,const pp&p2)
    {
        return p1.second>p2.second;
    }
    typedef priority_queue< pri::pp, pri::list, pri > queue;
};

static int f1(const int x){ return x==std::numeric_limits<int>().max()?-1:x; }

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,e;
        cin>>n>>e;
        pri::graph g(n+1);
        for(int i(0);i<e;i++){
            int u,v,w;
            cin>>u>>v>>w;
            g[u].push_back(pri::pp(v,w));
            g[v].push_back(pri::pp(u,w));
        }
        vector<int> d(n+1,std::numeric_limits<int>().max());
        int s;        cin>>s;
        d[s]=0;
        pri::queue q;
        q.push(pri::pp(s,d[s]));
        set<int> vs;
        while(!q.empty()) {
            const int u(q.top().first);
            const pri::list& gu(g[u]);
            q.pop();
            vs.insert(u);
            for( pri::list::const_iterator i(gu.begin()); i != gu.end(); ++i ) {
                const int v(i->first),  w(i->second);
                if( vs.find(v)==vs.end() ){
//                  cout<<u<<" "<<v<<" "<<w<<endl;
                    if( d[v]>d[u]+w ) {
                        d[v]=d[u]+w;
                        q.push(pri::pp(v,d[v]));
                    }
                }
            }
        }
        copy_if(d.begin()+1,d.end(),d.begin(),std::bind2nd(std::not_equal_to<int>(),0));
        transform(d.begin(),d.end()-2,ostream_iterator<int>(cout," "),f1);
        cout<<endl;
    }
    return 0;
}

- user3245269

Answer 6

基本上与其他答案相同，只是更详细一些--operator()代码定义了优先队列如何进行比较以确定队列中项目的优先级。使用这种框架，您可以定义一个优先队列来存储任何类型的对象，并且可以根据您想要的任何自定义排序对对象进行排序。

- user2566092