Floyd算法
BFS求01最短路
对于边权只有0和1的图，可以用BFS+deque求最短路
具体做法：前端队列存由0边更新的点，后端存由1更新的点，每次松弛从前端取
比较好想，由于是BFS，可以认为本层转移下，0边转移的点dis都相等，1边转移的点dis都相等（不一定正确），那么从前面取出来的点通过0边松弛了另一个点，dis值完全一样，放进队头也不会影响单调性，而1边松弛的点dis值+1又和后面的值一样，所以大致正确
本质上是dijkstra的特化版本
dijkstra算法
运用贪心策略，在未访问点集中选取距已访问点集最近的点，由此点拓展，堆优化后时间复杂度为\(O((n+m)logm)\)
void dijkstra() {
for(int i=1;i<=n;i++) dis[i]=INF;
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty()) {
int x=q.top().second;
q.pop();
if(vis[x]) continue; //这里注意不要重复访问，不然会TLE
vis[x]=1;
bfs(x) {
int v=e[i].to;
if(dis[v]>dis[x]+e[i].dis) {
dis[v]=dis[x]+e[i].dis;
if(!vis[v]) q.push(make_pair(dis[v],v));
}
}
}
}
最短路DAG
固定源点的所有点最短路的集合是DAG（易证）
利用该性质可以使用一些高效算法（拓扑，DP等）
注意:对于\(v\)点的第一次更新（\(dis[v]:\ INF\ -> dis[x]+e[i].dis\)）并不能保证\(dis[v]\)是\(v\)的最短路长；优先队列维护的是已完成更新的点集，因此取出的是\(dis[x]\)最小的点，并不能保证\(dis[x]+e[i].dis\)最小
因此应在dijkstra外建DAG
求路径，路径数
由于dijkstra算法是由源点向外拓展的，路径更新有连续性且形象易分析，所以常用于最短路计数
松弛的时候统计就好了
求次短路
Bellman-Ford算法
跑n次松弛操作，每次都把全部m条边松弛，由于最短路不会重复经过点，因此n次松弛后一定能找到最短路
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
if(dist[a]+w<dist[b])
dist[b] = dist[a] + w; //w是a->b的权重
}
判负环
由上文，我们进行第n+1次操作，如果还能松弛，说明走了重复点，即出现负环
加个flag看是否松弛即可
SPFA算法
基础
队列优化的Bellman-Ford，用队列存储点，找到可以松弛的边再把它连的点加进来。时间复杂度\(O(km)\)，遇到网格图会退化成\(O(nm)\)。
bool SPFA() {
for(int i=1;i<=n;i++) vis[i]=0,dis[i]=INF;
queue<int> q;
q.push(1)
while(!q.empty()) {
int x=q.front();
q.pop();
vis[x]=0;
bfs(x) {
int v=e[i].to;
if(dis[v]>dis[x]+e[i].dis) {
dis[v]=dis[x]+e[i].dis;
if(!vis[v]) {
q.push(v);
vis[v]=1;
}
}
}
}
return 0;
}
p.s.此份代码默认无负环，往往使用SPFA都是用于判负环。
注意加判是否入队，否则会重复操作
优化
1、DFS优化
广搜改深搜
2、SLF优化
3、LLL优化
判负环
1、边做最短路边判负环
一个点最多只能被n-1个点松弛入队，若入队次数>=n，则有重复经过，即找到负环。
在做最短路时加个cnt[]存入队次数即可。时间复杂度\(O(nm)\)。
bool SPFA() {
for(int i=1;i<=n;i++) dis[i]=1e9;
deque<int> q; //SLF优化
q.push_front(0);
vis[0]=1;
while(!q.empty()) {
int x=q.front();
q.pop_front();
vis[x]=0;
for(int i=head[x];i;i=e[i].next) {
if(dis[e[i].to]>dis[x]+e[i].dis) {
dis[e[i].to]=dis[x]+e[i].dis;
cnt[e[i].to]++;
if(cnt[e[i].to]>n) return 1; //找到负环
if(!vis[e[i].to]) {
if(!q.empty()&&dis[e[i].to]<dis[q.front()]) q.push_front(e[i].to);
else q.push_back(e[i].to);
vis[e[i].to]=1;
}
}
}
}
return 0;
}
2、只判负环
又看不懂了……
学长说用bfs版就ok（有朝一日我会来弄清楚这个问题的！）
与第一种判负环方法不同的是——BFS改DFS，初始化dis[]为0，再从每个点跑SPFA，每次跑不需要初始化dis[]。
1、初始化dis[]为0时，SPFA会且仅会进入负权子路径并松弛dis[]为负数，而负环也是负权子路径的一种，因此负环肯定能走到
由于是从每个点都跑，不会被某些正权边卡
当然，初始化dis[]为0注定了它不能跑最短路
2、每次跑不需要初始化dis[]是因为如果\(dis[v]>dis[x]+e[i].dis\)，那么松弛可能会使后面dis值更小，更有可能找到负环；相反，如果\(dis[v] \le dis[x]+e[i].dis\)，比现在搜出的dis[]还小的路径早就搜过了，那就完全没有进去搜的必要了
如果每次跑都清dis[]，那就会导致上面说的“没有搜的必要”的情况进去搜了，做无用功
最坏时间复杂度是\(O(nm)\)，但是往往达不到
bool SPFA(int x) {
vis[x]=1;
bfs(x) {
int v=e[i].to;
if(dis[v]>dis[x]+e[i].dis) {
dis[v]=dis[x]+e[i].dis;
if(vis[v]||SPFA(v)) return 1;
}
}
vis[x]=0;
return 0;
}
bool Check() {
for(int i=1;i<=n;i++) vis[i]=0,dis[i]=0;
for(int i=1;i<=n;i++) if(SPFA(i)) return 1;
return 0;
}