Dijkstra学习笔记
Creeper_l
·
·
个人记录
模板题：P4779
Dijkstra算法
### 做法
首先要定义松弛操作。对于一条边（$u,v$），松弛操作对应下面的运算：$dis_{v}$ = $dis_{u}$ + $w_{u,v}$。
对于$Dijkstra$，我们可以将结点分成两个集合：已确定最短路长度的点集（记为$S$集合）的和未确定最短路长度的点集（记为$ T$集合）。一开始所有的点都属于$T$集合。设源点为$s$，初始化$dis_{s} =0$，其他$dis$为正无穷。每一次从
$T$集合中选最短路最小的加入$S$集合中，并对其出边进行松弛操作，重复操作直到$T$集合为空为止。
### 证明
关于证明，可以用反证法，但我也不会证。主要是证明在执行操作时，取出的结点$u$最短路均已经被确定，即满足$D(u)$ = $dis(u)$。大概感性理解一下，因为每次选出的点都是$T$集合中最短路最小的点。具体证明可以参考[oiwiki](https://oiwiki.com/graph/shortest-path/#%E6%AD%A3%E7%A1%AE%E6%80%A7%E8%AF%81%E6%98%8E)。
### 时间复杂度
$Dijksra$有三种实现方法，一种是直接每次暴力寻找最短路最小的点，时间复杂度$O(n^{2} + m)$，这种方法时间复杂度很高，不常用。第二种是用优先队列优化，这种方法是最普遍的。因为每个点可能被修改多次，所以优先队列里的数是$O(m)$的，总复杂度$O(mlogm)$，可以接受。第三种是用线段树优化，支持单点修改和全局查询，时间复杂度$O(mlogn)$，但是码量比较大。
### Code
这里是用优先队列写的
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;
#define inf 0x3f3f3f3f
const int MAXN = 1e5 + 10;
int head[MAXN],cnt,n,m,x,y,z,dis[MAXN],s;
bool vis[MAXN];
struct Node
{
int u,v,w,nxt;
}e[MAXN << 1];
void add(int u,int v,int w){e[++cnt] = {u,v,w,head[u]};head[u] = cnt;}
priority_queue <pii,vector <pii>,greater <pii> > q;
void dijkstra(int s,int n)
{
memset(dis,inf,sizeof dis);
dis[s] = 0;
q.push(make_pair(n,s));
while(!q.empty())
{
int u = q.top().second
;q.pop();
if(vis[u] == true) continue;
vis[u] = true;
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(dis[u] + e[i].w < dis[now])
{
dis[now] = dis[u] + e[i].w;
q.push(make_pair(dis[now],now));
}
}
}
}
int main()
{
memset(head,-1,sizeof head);
cin >> n >> m >> s;
for(int i = 1;i <= m;i++) cin >> x >> y >> z,add(x,y,z);
dijkstra(s,0);
for(int i = 1;i <= n;i++) cout << dis[i] << " ";
return 0;
}
```