优先级队列和 dijkstra-解网

问：

向我解释如何构建优先级队列以及为什么您必须以这种方式构建，就好像我对优先级队列的经验的极限是知道队列是什么（我一生中从未使用过队列）。

当我看这个网站时： http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html

priority_queue<Time, vector<Time>, CompareTime> pq;

我知道时间是为了让你有一个时间队列，比较时间是决定将时间放入队列的优先级的原因，但为什么需要在构造函数中？vector<Time>

关于Dijkstra：我正在将一个图实现为节点的向量，每个节点都包含该向量中所有相邻位置的列表），所以它看起来像这样：

class Node {
  protected:
  string name;
  int value;
  list<int> nodes
}

我将如何实现 Dijkstra 的这一部分：

for each vertex v in Graph:                                
    dist[v] := infinity ;                               
    previous[v] := undefined ;

对于 dist[v] = 无穷大，我假设我将每个节点的值设置为无穷大，但是什么变量允许我这样做？对于 previous[v]，undefined 是什么意思？

C++

STEP1：设置

std::priority_queue有三个模板参数：

T：显然，存储在容器中的物品类型。
基础容器：顾名思义，是实现中使用的基础容器的类型。其默认值为。std::vector<T>
Comparer：priority_queue用于比较项目的 Functor 类。它的默认值是（因此，默认情况下，std：:p riority_queue 是最大优先级队列）。如果你想要一个最小优先级队列（就像你的例子一样，Dijkstra 的算法），你必须通过一个比较器来做到这一点。通常，你为你的类型实现二进制，以使函子工作。std::less<T>operator >std::greater<T>

STEP2：使用`std::priority_queue`

因此，如果您已经完成了设置，则可以使用。它有三个主要业务：std::priority_queue

push（）：在piority_queue中插入一个值。
pop（）：删除优先级队列的顶部。
top（）：返回对存储在priority_queue中的最大（或最小，取决于您的比较器）优先级的元素的常量引用。请注意，top（）不是 remove，它是 pop（） 的工作。

例：

#include <queue>
#include <iostream>

//User defined type. For this short example, a simple uint wrapper:
struct Foo
{
    unsigned int i;

    Foo(unsigned int _i) : i(_i) {}
};

//Implementation of operator> for class Foo, to make std::greater<Foo> work:
bool operator>(const Foo& f1 , const Foo& f2)
{
    return f1.i > f2.i;
}

int main()
{
    std::priority_queue<Foo,std::vector<Foo>,std::greater<Foo>> foo_min_priority_queue;

    foo_min_priority_queue.push(Foo(2));
    foo_min_priority_queue.push(Foo(1));
    foo_min_priority_queue.push(Foo(0));

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 0 
    foo_priority_queue.pop();

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 1 
    foo_min_priority_queue.pop();

    std::cout << foo_min_priority_queue.top().i << std::endl; //Prints 2 
    foo_min_priority_queue.pop();

    return 0;
}

引用：

我认为不可能将 STL 的优先级队列用于 Dijkstra 的算法，因为该算法需要对队列进行抽象操作。STL 的优先级队列既不提供此功能，也不提供删除任意元素以更新其优先级并再次插入的能力。为了实现高效的 Dijkstra 算法，斐波那契堆将是一个不错的选择。虽然 d-ary 堆足够简单，可以自己实现（使用数组）。decrease-key

1赞 phoeagon 7/7/2013

@android不是真的。即使队列中存在新元素，您仍然可以将新元素插入到优先级队列中。在实践中，我从未遇到过因此而出现的重大性能下降。

0赞 phoeagon 7/7/2013

而且我不认为比较器是必需的。默认情况下，返回最大值元素，因此您只需要存储距离的否定结果即可。priority_queue

上一个：模拟默认的 SharedPreferences

下一个：尝试在 for 循环中有 2 个列表迭代器

优先级队列和 dijkstra

priority queues and dijkstra

评论

评论

STEP1：设置

STEP2：使用`std::priority_queue`

例：

评论

优先级队列和 dijkstra

priority queues and dijkstra

评论

评论

STEP1：设置

STEP2：使用std::priority_queue

例：

评论

STEP2：使用`std::priority_queue`