- 上一篇：电脑屏幕出现条纹抖动是什么原因
- 下一篇：linux查看硬件信息命令
在有向图的处理中，通常会遇到一个非常棘手的问题——那就是遇到负环，许多最短路算法例如Dij和Floyd都不可以处理负环（包括堆优化的），这个时候我们可以怎样处理呢？通常来说最常见的方法是使用能够处理负环的方法B e l l m a n − F o r d Bellman-FordBellman−Ford和基于其的S p f a SpfaSpfa，但是有人会问，可不可以不用这些呢，有！那就是J o h n s o n JohnsonJohnson
（注意，加了堆优化的spfa处理不了负环）
好吧，听了下面之后你可能会想打我。。。
Johnson算法主要用于求稀疏图上的全源最短路径，其主体思想是利用重赋权值的方法把一个愿问题带负权的图转化为权值非负的图，然后再利用N NN次D i j k s t r a DijkstraDijkstra求出全源最短路径
下面讲一下重赋权值的具体步骤：
增设一虚点S，由S 往各点连一条权值为0的边
使用SSpfaSpfa求出点S SS到所有点的最短路，用h ( i ) h(i)h(i)表示
对于每条边，w ( u , v ) w(u,v)w(u,v)将其变成w ( u , v ) ‘ = w ( u , v ) + h ( u ) − h ( v ) w(u,v)`=w(u,v)+h(u)-h(v)w(u,v)‘=w(u,v)+h(u)−h(v)
这一理论最坏的时间复杂度为O ( n m ) O(nm)O(nm)，这样我们就把问题转化为在一张非负图上求全源最短路径，是一个十分优秀的算法
如果用斐波那契推，时间复杂度为O ( N M + N 2 l o g N + N M ) = O ( N M + N 2 l o g N ) O(NM+N^2logN+NM)=O(NM+N^2logN)O(NM+N
logN+NM)=O(NM+N
logN)
如果用二叉堆推，时间复杂度为O ( N M + N 2 l o g N + N M l o g N ) = O ( N ( N + M ) l o g N ) O(NM+N^2logN+NMlogN)=O(N(N+M)logN)O(NM+N
logN+NMlogN)=O(N(N+M)logN)
#include<queue>
#include<cstdio>
#define IL inline
#define LL long long
#define M 300501
using namespace std;int ans[701][701],n,m,x,y,z,l[701],tot,h[702],S;
LL f;char c;
struct node{int from,next,to,w;}e[M];
queue<int>q;
bool vis[701];
void add(int u,int v,int w)
{
e[tot]=(node){u,l[u],v,w};l[u]=tot++;
return;
}
IL LL read()//输入流
{
f=0;
while(c=getchar(),c<=47||c>=58);f=(f<<3)+(f<<1)+c-48;
while(c=getchar(),c>=48&&c<=57) f=(f<<3)+(f<<1)+c-48;
return f;
}
void write(LL x){if(x>9) write(x/10);putchar(x%10+48);return;}
void spfa()//Spfa
{
h[S]=0;q。push(S);vis[S]=true;
while(q。size())
{
int x=q。front();q。pop();vis[x]=true;
for(int i=l[x];i;i=e[i]。next)
{
int y=e[i]。to,w=e[i]。w;
if(h[x]+w<h[y])
{
h[y]=h[x]+w;
if(!vis[y]) vis[y]=true,q。push(y);
}
}
vis[x]=false;
}
}
void johnson()//johnson算法
{
spfa();
for(int i=1;i<=m;i++) ans[e[i]。from][e[i]。to]=ans[e[i]。from][e[i]。to]+h[e[i]。from]-h[e[i]。to];return;
}
int main()
{
n=read();m=read();S=n+1;
for(int i=1;i<=n;i++) add(S,i,0),h[S]=1e9;
for(int i=1;i<=m;i++) x=read(),y=read(),z=read(),add(x,y,z),ans[x][y]=z;
johnson();
}