堆优化的Dijkstra

核心 - 图论的基本方程

问：在图中，$s\rightarrow t$最短路径是多少。

每一个点有一个$d(u)$（Distance），则对于所有边，有

$$d(u) = \min\{d(v) + w(v, u)\}$$

算法解释

• 上述方程可以展开写成$n$个方程构成的方程组，而Dijkstra算法则完成了这一过程。
• Dijkstra方法可以理解为：从已知点出发，不断地从已知量计算未知量，因为是$\min$操作，我们每次都先取最小的值。
• 具体如下图：

Ref 地址

关于堆优化

堆优化用在每次寻找当前dis数组中最小值的时候。所以我们需要维护一个小根堆，这将时间复杂度从$O(n^2)$降到了$O(n\log n)$

关于小根堆的实现

1. 黑魔法：放入相反数，别忘了取的时候乘-1
2. 正常人做法：priority_queue<int, vector<int>, greater<int> > q;
3. 详见我的代码（直接在结构体当中重新定义运算符）

代码

int ecnt = 2; // 这也是黑魔法，直接0就行了
int n, m, k, s, t;
int head[150005], dis[150005], vis[150005];
struct edge { int to, next, w; } g[300010];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }

struct node {
	int dis, pos;
    // 前文提到的黑魔法
	friend bool operator < (const node &a, const node &b) { return a.dis > b.dis; }
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 0; i <= n; i ++) dis[i] = 8e18;
	dis[s] = 0; q.push((node) { dis[s], s });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
            // 图论基本方程
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				q.push((node) { dis[v], v });
			}
		}
	}
}

注：其中，单源最短路的源是s。