以spfa为例
1.把energy取相反数 求最短路
2.为保证不在路上挂掉 对dist[t]+w>=0的点不予更新
3.如果出现负环 则把负环节点取一极小值 然后最后一次push这个点

参考程序

bool spfa(int s){
     int i,t,u,w;
     while(!q.empty())q.pop();
     for(i=0;i<N;i++)dist[i]=inf;
     memset(used,false,sizeof(used));
     memset(cnt,0,sizeof(cnt));
     cnt[s]=1;
     dist[s]=-100;
     q.push(s);
     while(!q.empty()){ 
         t=q.front();
         if(t==N-1 && dist[t]<0)return true;
         q.pop();
         used[t]=false;
         for(i=p[t];i!=-1;i=e[i].next){
             u=e[i].u;
             w=e[i].c;
             if(dist[t]+w<0 && dist[t]+w<dist[u]){
                 dist[u]=dist[t]+w;
                 if(!used[u]){
                      used[u]=true;
                      cnt[u]++;
                      if(cnt[u]>=N){
                          dist[u]=-inf;
                          if(cnt[u]==N)q.push(u);
                      }        
                      else q.push(u);
                 }
             }
         }
     }
     if(dist[N-1]<0)return true;
     else return false;
}