SPFA
给定一张 \(n\) 个点、\(m\) 条边的有向图，求 \(1\) 号点到每个点的最短路径长度。
我们用 \(dis_{i}\) 表示从点 \(1\) 到点 \(i\) 的最短距离。
-
初始化 \(dis_{1}\) 为 \(0\)，其余为无穷大，搞一个队列并将起点入队
-
取队头 \(x\)，遍历它的出边 \(x\) 至 \(y_i\) ，若 \(dis_{y_i}>dis_x+w_{x,y_i}\), 则 \(dis_{y_i}\gets dis_x+w_{x,y_i}\) 并将 \(y_i\) 入队
-
重复第二步，直到队列为空
如果起点不是 \(1\) ，就按需求调整起始点。
复杂度为 \(O(kn)\)，注意可能退化到 \(O(nm)\)，可以搞负权
spfa粗浅的证明
迭代思想，最后这个图肯定满足三角不等式
int n, m, u, v, w;
vector<int>to[MN], eg[MN];
int dis[MN]; bool vis[MN];
queue<int>q;
void spfa() {
for(int i=1; i<=n; ++i) dis[i]=INF, vis[i]=0;
dis[1]=0; q.push(1);
while(q.size()) {
int val=q.front(); q.pop();
for(int i=0; i<to[val].size(); ++i) {
int j=to[val][i], k=eg[val][i];
if(dis[j]>dis[val]+k) {
dis[j]=dis[val+k];
q.push(j);
}
}
}
}