1. 全栈程序员必看首页

浅谈Johnson算法

全栈程序员-站长 • • 未分类 • 阅读 2

浅谈Johnson算法在有向图的处理中 通常会遇到一个非常棘手的问题 那就是遇到负环 许多最短路算法例如 Dij 和 Floyd 都不可以处理负环 包括堆优化的 这个时候我们可以怎样处理呢 通常来说最常见的方法是使用能够处理负环的方法 Bellman Ford 和基于其的 Spfa 但是有人会问 可不可以不用这些呢 有 那就是 Johnson

在有向图的处理中，通常会遇到一个非常棘手的问题——那就是遇到负环，许多最短路算法例如Dij和Floyd都不可以处理负环（包括堆优化的），这个时候我们可以怎样处理呢？通常来说最常见的方法是使用能够处理负环的方法 B e l l m a n − F o r d Bellman-Ford Bellman−Ford和基于其的 S p f a Spfa Spfa，但是有人会问，可不可以不用这些呢，有！那就是 J o h n s o n Johnson Johnson
（注意，加了堆优化的spfa处理不了负环）
好吧，听了下面之后你可能会想打我。。。




J o h n s o n Johnson Johnson算法主要用于求稀疏图上的全源最短路径，其主体思想是利用重赋权值的方法把一个愿问题带负权的图转化为权值非负的图，然后再利用 N N N次 D i j k s t r a Dijkstra Dijkstra求出全源最短路径

下面讲一下重赋权值的具体步骤：

  1. 增设一虚点 S S S，由 S S S往各点连一条权值为0的边
  2. 使用 S p f a Spfa Spfa求出点 S S S到所有点的最短路，用 h ( i ) h(i) h(i)表示
  3. 对于每条边， 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+N2logN+NM)=O(NM+N2logN)

如果用二叉堆推，时间复杂度为 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+N2logN+NMlogN)=O(N(N+M)logN)

代码

#include 
     #include 
     #define IL inline #define LL long long #define M  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(); }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/220636.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 下午8:00
下一篇 2026年3月17日 下午8:00


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号