观看前提示：本人的码风可能会引起您的不适。
写作时间：2022-9-10~2022-10-12.
1.Floyd全源最短路
1-1 朴素
弗洛伊德，枚举每个点然后进行松弛，这样可以在 \(\Theta(n^{3})\) 时间里求出每个点的最短路。
写起来很像dp。
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
ans[j][k]=min(ans[j][k],ans[j][i]+ans[i][k]);
}
}
}
这是最朴素的Floyd算法，时间复杂度为 \(\Theta(n^3)\)。
Floyd算法优化也有，但是实际上对时间复杂度的优化并没有多少。
如果要考Floyd，数据范围不会很大的。
切记切记。
1-2 传递闭包
这东西只需要改改条件罢。
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
if(ans[j][i] && ans[i][k])
{
ans[j][k]=1;
}
}
}
}
2.dijkstra单源最短路算法
2-1 朴素
void dijkstra(int u)
{
queue<int>q;
fill(dis,dis+n,2147483647);
dis[u]=0;
vis[u]=1;
q.push(u);
while(q.empty()==false)
{
int cur=q.front();
q.pop();
vis[cur]=0;
for(int i=head[cur];i;i=e[i].nxt)
{
int v=e[i].v;
int w=e[i].w;
if(dis[v]>dis[cur]+w)
{
dis[v]=dis[cur]+w;
pre[cur]=v;
if(vis[v]==0)
{
vis[v]=1;
q.push(v);
}
}
}
}
}
我们使用了一个队列来让当前节点入队。
时间复杂度为 \(\Theta(n^{2})\)
2-2 堆优化/优先队列优化
比较广泛的是堆优化。
fill(dis,dis+BI,iINF);
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
int tmp=q.top().second;
q.pop();
if(vis[tmp])
{
continue;
}
vis[tmp]=1;
for(int i=head[tmp];i;i=e[i].nxt)
{
int v=e[i].v;
int w=e[i].w;
if(dis[v]>dis[tmp]+w)
{
dis[v]=dis[tmp]+w;
q.push(make_pair(-dis[v],v));
}
}
}
这一段代码中，q是一个优先队列，它的定义是：
priority_queue<pair<int,int>>q;
省去了查找最大值，时间复杂度为 \(\Theta((n+m)\log n)\)。
一般使用优先队列优化的 Dijkstra，因为并没有难写多少，而且时间复杂度更优，绝大多数时候堆优化的Dijkstra就够了。
缺点是边权不能为负数。
3.SPFA及其优化
3-1
我们都知道，朴素的SPFA及其容易被卡：
fill(dis,dis+n,2147482347);
int spfa()
{
queue<int>q;
q.push(1);
dis[1]=0;
vis[1]=true;
while(q.size())
{
int u=q.front();
q.pop();
vis[t]=false;
for(int i=head[u];i;i=e[i].nxt)
{
int j=e[i].v;
if(dis[j]>dis[t]+e[i].w)
{
dis[j]=dis[t]+e[i].w;
if(!vis[j])
{
vis[j]=true;
q.push(j);
}
}
}
}
if(dis[n]==2147482347)
{
return -1;
}
return dis[n];
}
如果没有被卡，时间复杂度是 \(\Theta(k\times m)\)，一般情况下，\(k\) 大约在 \(1-20\) 之间。
但是非常容易被卡，时间复杂度会退化到 \(\Theta(n\times m)\)，这个时候无法通过大部分数据。
所以SPFA这个东西，实际上是不靠谱的。
但是它能够用来判断负环，对于差分约束系统是很有用的。
3-2 优化
3-2-1 SLF
直接把
queue<int>q;
改成
deque<int>q。
int spfa()
{
deque<int>q;
q.push_back(1);
dis[1]=0;
vis[1]=true;
while(q.size())
{
int u=q.front();
q.pop_front();
vis[t]=false;
for(int i=head[u];i;i=e[i].nxt)
{
int j=e[i].v;
if(dis[j]>dis[t]+e[i].w)
{
dis[j]=dis[t]+e[i].w;
if(!vis[j])
{
vis[j]=true;
q.push_back(j);
}
}
}
}
if(dis[n]==2147482347)
{
return -1;
}
return dis[n];
实际上并没有优化多少，还是很容易被卡到 \(\Theta(n\times m)\).
3-2-2 LLL
不是很会写，这实际上是LLL+SLF，朴素LLL优化把队列换回queue就好了。
void spfa()
{
int u,v,num=0;
long long x=0;
list<int>q;
for(int i=1; i<=n; i++)
{
dis[i]=MAX;
vis[i]=false;
}
dis[s]=0;
vis[s]=true;
q.push_back(s);
num++;
while(!q.empty())
{
u=q.front();
q.pop_front();
num--;
x-=dis[u];
while(num&&dis[u]>x/num)
{
q.push_back(u);
u=q.front();
q.pop_front();
}
vis[u]=false;
for(int i=head[u]; i; i=e[i].next)
{
v=e[i].to;
if(relax(u,v,e[i].w)&&!vis[v])
{
vis[v]=true;
if(!q.empty()&&dis[v]<dis[q.front()])
{
q.push_front(v);
}
else
{
q.push_back(v);
}
num++;
x+=dis[v];
}
}
}
for(int i=1; i<=n; i++)
{
printf("%d ",dis[i]);
}
printf("\n");
}
还是很容易被卡，但是起码被卡之后比朴素快一点。
3-2-3
NTR算法，来自知乎Raffica的写法
对，不过不如尝试以下奇怪的方法来避免被卡：（原创！）维护一个叫临时最短路树的东西，刚开始只有一个源节点这SPFA的过程中，每次松弛(u, v)边时将v的父亲设为u；v是有可能有后代的，所以将其所有后代的对应inqueue标记清除；在SPFA过程中如果发现队头节点的inqueue为空那么跳过。理由是如果我们能松弛(u, v)边，那么从(u, v)走势必比以前走过的那种走法好。将这个步骤称为NTR。
以上为用lct实现的这东西的代码的一部分（当时在测试lct模板 事实上正常来讲用lct反而更慢（说明 最终不用lct）
当有负权环时这个算法也会出现环，所以可以用来快速找环。
这个算法会被奇怪的图卡掉。但是网格图卡不掉。
作者：Raffica
转载注明出处。
int SPFA()
{
int i, j, x, cnt = 0;
queue<int> Q;
memset(d, 0x3f, sizeof(d));
d[S] = 0;
Q.push(S);
setv(S, 1);
while(!Q.empty())
{
x = Q.front();
Q.pop();
cnt ++;
if(!query(x)) continue;
for(i = 0;i < G[x].size();i ++)
{
Edge &e = edge[G[x][i]];
if(d[x] + e.w < d[e.v])
{
d[e.v] = d[x] + e.w;
Q.push(e.v);
setc(e.v, 0);
setv(e.v, 1);
if(lca(e.v, x) == e.v)
{
return 0;
}
int f = getfa(e.v);
linkcut(f, e.v, x);
}
}
}
return 1;
}
时间复杂度貌似是 \(\Theta(n\log n\log (m/n)+m)\)，即 \(\Theta(n\log n\log (m/n))\) 试了一下是能过hack数据的。
3-2-4 SLFS
就是SLF加上了一个swap算法，实际实现可以看CSDN扩展的灰的代码
void work()
{
int l,r;
t=1;l=r=0;
memset(dis,iINF,sizeof(dis));
dis[s]=0;
q[r++]=s;
while(l!=r)
{
int u=q[l++];
if(l>n)
{
l=0;
}
if(cnt[u]>t)
{
q[r++]=u;
if(r>n) r=0;
t+=20;
continue;
}
vis[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
int w=e[i].w;
int d=dis[u]+w;
if(d<dis[v])
{
dis[v]=d;
if(!vis[v])
{
q[r++]=v;
++cnt[u];
if(r>n)
{
r=0;
}
vis[v]=1;
}
int rr;
if(r-1<0)
{
rr=n;
}
else
{
rr=r-1;
}
if(dis[q[l]]>dis[q[rr]])
{
swap(q[l],q[rr]);
}
}
}
}
for(int i=1;i<=n;++i)
{
put(dis[i]);
putchar(' ');
}
}
每当队列改变时，如果队首距离大于队尾，则交换首尾。
这个 SLF 看起来很弱，但却通过了所有 Hack 数据。而且，非常难卡。
能够过掉hack数据，但是实际上还是能卡的。
3-2-5 堆优化
一般的算法都是让队列接近优先队列，现在是直接定义一个优先队列。
void SPFA()
{
priority_queue<int, vector<int>, cmp> q;
q.push(s);
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
vis[s] = true;
while (!q.empty())
{
int u = q.top();
q.pop();
vis[u] = false;
for (int i = 0; i < v[u].size(); i++)
{
if (dis[v[u][i]] <= dis[u] + w[u][i]) continue;
dis[v[u][i]] = dis[u] + w[u][i];
if (vis[v[u][i]]) continue;
q.push(v[u][i]);
vis[v[u][i]] = true;
}
}
}
这里的cmp函数按照dis来排序。
复杂度正确，能通过hack数据。
3-2-6 乱序
加一个
for(int i = 1 ; i <= n ; i++)
{
random_shuffle(e[i].begin() ,e[i].end());
}
3-2-7 mcfx 优化
在第 \([ l,r]\) 次访问一个结点时，将其放入队首，否则放入队尾。通常取 \(l=2,r=\sqrt{v}\) 。
写不来，溜了。
3-2-8 SLF容错优化
每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾。
我们定义容错值 \(val\)，当满足 \(dis[now]>dis[q.front()]+val\) 时从队尾插入，否则从队首插入。
设w为边权之和，\(val\) 一般为 \(\sqrt{w}\)
容错SLF可以让你的程序不陷入局部最优解，与模拟退火类似
3-2-9 随机化优化
除了乱序以外：
队列随机：每个节点入队时，以0.5的概率从队首入队，0.5的概率从队尾入队。
队列随机优化版：每 \(x\) 次入队后，将队列元素随机打乱。
3-3 Hack it!
显然，普通 SPFA 是非常好卡的，只需要一个随机网格图即可。
当你用到优化的时候，也就不用卡了。
3-4 用途
- 判负环;
- 如果边权有时候为负的单源最短路只能首选SPFA。
- 求最小费用最大流
- 次短路...?
- 没了，用Dijkstra。
4.johnson全源最短路
和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。
可以说是一种集大成者。
我们新建一个虚拟节点（在这里我们就设它的编号为\(0\)）。从这个点向其他所有点连一条边权为\(0\)的边。
接下来用SPFA算法求出从\(0\)号点到其他所有点的最短路，记为 \(dis\)
假如存在一条从点 \(u\) 到点 \(v\)，边权为 \(w\) 的边，则我们将该边的边权重新设置为 \(w += dis[u] - dis[v]\);
接下来以每个点为起点，跑 \(n\) 轮 Dijkstra 算法即可求出任意两点间的最短路了。
最后加上 \(dis[v] - dis[u]\);
容易看出，该算法的时间复杂度是 \(\Theta(nm\log m)\)。
//火车头省略。
struct node
{
int dis;
int id;
bool operator<(const node& a) const
{
return dis > a.dis;
}
node(int d, int x)
{
dis = d, id = x;
}
}
int head[5005];
int vis[5005];
int t[5005];
int cnt, n, m;
int h[5005];
int dis[5005];
void add(int u, int v, int w)
{
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
bool spfa(int s)
{
queue<int> q;
fill(h,h+KI,iINF)
h[s] = 0, vis[s] = 1;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
if (h[v] > h[u] + e[i].w)
{
h[v] = h[u] + e[i].w;
if (!vis[v])
{
vis[v] = 1;
q.push(v);
t[v]++;
if (t[v] == n + 1) return false;
}
}
}
}
return true;
}
void dijkstra(int s)
{
priority_queue<node> q;
fill(dis,dis+KI,iINF);
memset(vis, 0, sizeof(vis));
dis[s] = 0;
q.push(node(0, s));
while (!q.empty())
{
int u = q.top().id;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
if (dis[v] > dis[u] + e[i].w)
{
dis[v] = dis[u] + e[i].w;
if (!vis[v])
{
q.push(node(dis[v], v));
}
}
}
}
return;
}
int main()
{
for (int i = 1; i <= m; i++)
{
int u=read();
int v=read();
int w=read();
add(u, v, w);
}
for (int i = 1; i <= n; i++)
{
add(0, i, 0);
}
if (!spfa(0))
{
cout << -1 << endl;
return 0;
}
for (int u = 1; u <= n; u++)
{
for (int i = head[u]; i; i = e[i].next)
{
e[i].w += h[u] - h[e[i].v];
}
}
for (int i = 1; i <= n; i++)
{
dijkstra(i);
long long ans = 0;
for (int j = 1; j <= n; j++)
{
if (dis[j] == INF)
ans += j * INF;
else
ans += j * (dis[j] + h[j] - h[i]);
}
cout << ans << '\n';
}
return 0;
}