Dijkstra单源最短路堆优化算法

Dijkstra单源最短路堆优化算法

使用基于堆的优先队列，我们可以在进行松弛操作前对找边进行优化操作

时间复杂度为 \(O(m\log m)\) ，其中 \(m\) 为边的数量，优先队列找边的时间复杂度为\(O(\log m)\)

优先队列

默认为一个大根堆，即堆顶的元素的优先级最高，体现在某个变量的值上

每次从队列中取出堆顶元素，我们依据堆的特性，可以选出当前最优的节点，再对这个节点进行访问，对其可联通点进行一轮松弛操作，最后将这些点依次压入队列中，优先队列会帮助我们将这些点进行优先级排序

对于Dijkstra而言，我们将节点放入优先队列中，我们的边权w作为的是优先级评判变量，但是，我们最优考虑的点为边权最小的点，所以这就有两种办法来解决这个问题

• 将边权取负后放入队列
• 使用重载运算符，实现小根堆的优先队列

介绍第一种操作：

边权作为优先队列的优先级依据，它的值越大优先级越高，我们需要值越小（当前最优）的边优先级最高，所以可以先对边权取负再放入队列中

priority_queue<pair<int, int>> q;//二元组队列，存储边权和联通点
void dijkstra(int s) {
	presetdis();//预处理距离
	q.push({ 0,s });//起始点到自己的距离为0，压入队列
	dis[s] = 0;
	while (q.size())//当队列不空时
	{
		auto t = q.top();//取出堆顶元素
		q.pop();//弹出堆顶元素
		if (vis[t.second]) continue;//如果堆顶元素这个节点已被访问过，重新取元素
		vis[t.second] = 1;//标记这个节点已被访问
		for (auto it = e[t.second].begin(); it != e[t.second].end(); it++) {//迭代访问
			dis[it->v] = min(dis[t.second] + it->w, dis[it->v]);//松弛操作
			q.push({-(dis[it->v]),it->v});//压入更新后的节点
		}
	}
}

其中，first存储边权，second记录联通点，优先队列默认以pair的first作为优先级标准

q.push({-(dis[it->v]),it->v})对权值取负，即依靠大根堆直接排序

重载运算符的操作

先来看一下priority_queue的原型声明

其中的 Type为数据类型，Container为容器（vector,deque...），Functional为比较方式

priority_queue<Type, Container, Functional>

对于一般的独立变量而言，构造小根堆只需要在默认的大根堆写法上稍加修改

priority<int> q;//大根堆
priority<int, vector<int>, greater<int> > q;//小根堆

处理结构体变量时，需要更复杂的操作，使优先队列依照结构体内的某个成员进行优先级排序

这里使用的是定义 cmp 函数，重载运算符来进行小根堆的实现

struct node{
    int x;
    int y;
};
struct cmp{
    bool operator()(node a,node b){
        return a.x > b.x;
    }
};
priority_queue<node,vector<node>,cmp> q;

struct cmp 定义了一个自定义的比较器，operator() 是一个重载运算符，允许 cmp 作为函数对象使用

接收两个 node 对象 a 和 b，如果 a.x 大于 b.x 就返回 true ，优先队列将根据 x 的值进行排序，较小的 x 值优先

注意，这里的 cmp 函数逻辑和 sort 中的 cmp 的逻辑相反

bool compare(node a, node b) {
    return a.x > b.x; // 降序排序，大的值在前
}
//当 a.x 大于 b.x 时，返回 true,表示在优先队列中，a 不是优先于 b 的

bool operator()(node a, node b) {
    return a.x > b.x;// 小根堆，大的值优先级更低
}
当 a.x 小于 b.x 时，返回 true，表示 a 在 b 之前

也可以将重载运算符的操作放在结构体内

struct node{
    int x;
    int y;
    bool operator<(const node &a) const
    {
        return x>a.x;
    }
};
priority_queue<node> q;

node 的 x 值被用来进行比较，这里是 x > a.x，表示当 x 值较大时会被认为是“优先级较小”的

优先队列在处理 node 时，将会以 x 值从大到小的顺序排列