给定一张 \(n\) 个点、\(m\) 条边的有向图，求 \(1\) 号点到每个点的最短路径长度。
我们用 \(dis_{i}\) 表示从点 \(1\) 到点 \(i\) 的最短距离。
-
初始化 \(dis_{1}\) 为 \(0\)，其余为无穷大
-
找出点 \(i\) ,满足 \(dis_{i}\) 是未标记节点中 \(dis\) 值最小的，并标记点 \(i\)
-
遍历节点 \(i\) 的出边，有点 \(i\) 到点 \(j\)，权值为 \(k\)。
若 \(dis_{j}>dis_{i}+k\)，更新 \(dis_{j}\) 为 \(dis_{i}+k\) -
重复第二第三步，标记到不能标记
如果起点不是 \(1\) ，就按需求调整起始点。
对于第二步，我们可以暴力循环但显然时间复杂度高，因此我们选用堆来存 \(dis\) 的值，以此优化，堆优化后的 Dijkstra 时间复杂度是 \(O(n\log n)\)，没有优化的是 \(O(n^2)\)。
不可以搞负权
Dijkstra粗浅的证明
因为边权都为非负数，所以选取的 \(dis\) 最小的结点不可能被其他点更新，故每次选出来的点 \(i\) 对应的 \(dis_{i}\) 一定是从起点到 \(i\) 的最短距离。
int n, m, u, v, w;
vector<int>to[MN], eg[MN];
int dis[MN]; bool vis[MN];
priority_queue<pair<int,int> >q;
void dij() {
for(int i=1; i<=n; ++i) dis[i]=INF, vis[i]=0;
dis[1]=0; q.push(make_pair(0,1));
while(q.size()) {
int x=q.top().second; q.pop();
if(vis[x]) continue;
vis[x]=true;
for(int i=0; i<to[x].size(); ++i) {
int y=to[x][i], z=eg[x][i];
if(dis[y]>dis[x]+z) {
dis[y]=dis[x]+z;
q.push(make_pair(-dis[y],y));
}
}
}
}