Dijkstra

---

前置知识

• 堆
• 图论基础
• Bellman-Ford

---

思路

Dijkstra 算法是一种求正权图单源最短路的算法。

注意到BF最大的缺陷在于其对于一个点的松弛方式太暴力了。
注意到有正权这个条件。
那么我们发现，只要选取当前距离最小的点，该点不可能被松弛。
于是使用一个小根堆维护距离即可。

---

算法参数

• 时间复杂度：$O(m\log n)$
• 空间复杂度：$O(n+m)$

---

实现代码

struct node{int u,d;};
bool operator<(node a,node b){return a.d>b.d;}
void Dijkstra(int s){memset(dis,0x3f,sizeof(dis));dis[s]=0;priority_queue<node> q;q.push({s,0});while (!Q.empty()){node cur=q.top();q.pop();int u=fr.u,k=fr.d;if (k!=d[u]) continue;for (node e:G[u]){int v=e.v,w=e.w;if (d[u]+w<d[v]){d[v]=d[u]+w;q.push({v,d[v]});}}}
}

---

练习

• P3371
• P4779
• P1339