图论中的常见算法分析比较和模板 - c++编程基础

ight w in edges: if distance[u] + w < distance[v]: distance[v] := distance[u] + w predecessor[v] := u // 步骤3：检查负权环 for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: error "图包含了负权环"

改算法同样也有一个很常用的优化算法SPFA算法，就是将检查的时候常常用FIFO来代替了循环检查。

/*
    Head[]为邻接表的表头
    Key[] 为邻接表的顶点
    Next[]为邻接表的下个节点
    w[]   为该点的权重
*/
void SPFA(int s)              //s 为起点
{
    queue
  
    q;
    int c[MAXV];           //判断是否有负环
    bool inq[MAXV];        //在队列中的标记
    for(int i = 0;i < n;++i)
      d[i] = (i==s 0:INF);
    memset(inq,0,sizeof(inq));
    q.push(s);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        inq[x] = 0;                   //清除在队列中的标记
        for(int e = Head[x];e != -1;e = Next[e])if(d[Key[e]] > d[x]+w[e]){
            d[Key[e]] = d[x] + w[e];
            if(!inq[Key[e]]){          //如果已经在队列中，就不要重复加了
               inq[Key[e]] = 1; 
               c[Key[e]]++;
               if(c[Key[e]] > MaxVerter)
                  RETURN "有负环"
               q.push(Key[e]);     
            }
        }
    }
}

判断有无负环：如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）

图论中的常见算法分析比较和模板(二)