最短路总结

背景：

只是想来备份一下最近的代码，顺便总结一下三种最短路算法的应用。

基础代码：

dijkstra:

 1 struct nd{int d,u; bool operator < (const nd &a)const{return d>a.d;}};
 2 int d[maxn]; bool vis[maxn]; priority_queue<nd>q;
 3 void dijkstra(int s){
 4     inc(i,1,n)d[i]=INF; d[s]=0; q.push((nd){0,s});
 5     while(!q.empty()){
 6         int x; while(!q.empty()&&vis[x=q.top().u])q.pop(); if(vis[x])break; vis[x]=1;
 7         for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){
 8             d[es[i].t]=d[x]+es[i].w; q.push((nd){d[es[i].t],es[i].t});
 9         }
10     }
11 }

spfa(bfs+slf):

 1 ll d[maxn]; bool inq[maxn]; deque<int>q;
 2 ll spfa(){
 3     inc(i,1,n)d[i]=INF; d[1]=0; inq[1]=1; q.push_back(1);
 4     while(!q.empty()){
 5         int x=q.front(); q.pop_front(); inq[x]=0;
 6         for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){
 7             d[es[i].t]=d[x]+es[i].w;
 8             if(!inq[es[i].t]){
 9                 if(!q.empty()&&d[es[i].t]<d[q.front()])q.push_front(es[i].t);else q.push_back(es[i].t);
10                 inq[es[i].t]=1;
11             }
12         }
13     }
14     return d[n];
15 }

spfa(dfs):

 1 bool ins[maxn],f; double d[maxn];
 2 void dfs(int x){
 3     ins[x]=1;
 4     for(int i=g[x];i;i=es[i].n){
 5         if(f)return;
 6         if(d[es[i].t]>d[x]+es[i].w){
 7             if(ins[es[i].t]){f=1; return;} d[es[i].t]=d[x]+es[i].w; dfs(es[i].t);
 8         }
 9     }
10     ins[x]=0;
11 }
12 bool spfa(){
13     memset(ins,0,sizeof(ins)); memset(d,0,sizeof(d)); f=0;
14     inc(i,1,n){dfs(i); if(f)return 0;} return 1;
15 }

floyd:

1 inc(k,1,n)inc(i,1,n)inc(j,1,n)if(map[i][k]+map[k][j]<map[i][j])map[i][j]=map[i][k]+map[k][j];

比较：

dijkstra:

本算法的优点就是快，没有什么一定需要其解决的问题，且只能处理正权边及求最短路（不能求最长路）。复杂度为O(mlog₂n)不过常数会稍大。

spfa：

优点是可以处理负权边以及判负环，当不用判负环时bfs+slf（双端队列优化）的最坏复杂度是O(nm)，但是常数很小，有时快过dijkstra。当需要判负环时bfs+slf复杂度经常会达到最坏复杂度，这时候用dfs写法会明显快很多，因为在不连通图中判负环需要每个点都作为源点跑一次。

floyd：

优点是短，可以用一行求出两两点的最短路，复杂度O(n³)且常数很小。

常见模型：

差分约束系统：

n个数，知道他们两两之间形如ai-aj≥c，ai-aj≤c的关系，求n个数最小/最大是多少。解法：如果是求最大值，则将所有限制条件转化为为≤，将得到的i和j连边，权值为c并跑最短路，因为得到的是满足条件的最大值；如果是求最小值，则将所有限制条件设定为≥，将得到的i和j连边，权值为c并跑最长路，因为得到的是满足条件的最小值。

01分数规划：

n点m边有向图，点有点权，边有边权，从某点出发，走一些路使得经过的点权和除以（浮点数除法）边权和最大或最小，求这个小数（保留两位）。解法：假设需要所求小数最大，那么二分这个数，然后将所有边的边权改为分母（需要最小化的部分）*二分的数-分子（需要最大化的部分），然后判负环。如果有，说明解合法，否则解不合法。最后把下界输出。如果需要所求小数最小，则把边权改为分子（需要最大化的部分）-分母（需要最小化的部分）*二分的数，同时改变范围缩小的方向。

倍增floyd：

从s到t，要求刚好经过k条边，求最短路。解法：把用floyd的方式对两个邻接矩阵进行合并定义成一个运算，则答案为初始矩阵与自己做k次运算得到的结果。而该运算符合结合律，故可以用类似矩阵快速幂的方法刚好做log₂k次运算。