本文共 1668 字，大约阅读时间需要 5 分钟。

下面有两种写法不同的时间复杂度可以根据自己的理解程度去选择

第一种：

void Add(int u,double cost,int v)//邻接表存储关系{    w[top] = cost;    Key[top] = v;    next[top] = head[u];    head[u] = top++;}bool SPFA(int x){    memset(vis,false,sizeof(vis));    memset(inq,0,sizeof(inq));    queue
   
     Q;    for(int i = 1;i <= n;i++) dis[i] = (i == x ? 0 : INF);    vis[x] = true;    inq[x] = 1;    Q.push(x);    while(!Q.empty())    {        int cur = Q.front();        Q.pop();        vis[cur] = false;        for(int e = head[cur] ; e != -1; e = next[e])        {            int v = Key[e];            if(dis[v] < dis[cur] * w[e])            {                dis[v] = dis[cur] * w[e];                if(!vis[v])                {                    inq[v] ++;                    if(inq[v] >= n) return true;//如果入队次数超过n-1次说明存在环或负权                    Q.push(v);                    vis[v] = true;                }            }        }    }    return false;}
   

第二种

初始化 map 为正无穷

bool SPFA(int x){    queue
   
     Q;    memset(vis,false,sizeof(vis));    memset(in,false,sizeof(in));    for(int i = 1;i <= n;i++)   dis[i] = （i==x?0: INF);    vis[x] = true;    Q.push(x);    in[x] = 1;    while(!Q.empty())    {        int cur = Q.front();        Q.pop();        vis[cur] = false;        for(int i = 1;i <=n;i++)        {            if(map[cur][i]!=-INF&&dis[i] < dis[cur] * map[cur][i])            {                dis[i] = dis[cur] * map[cur][i];                if(!vis[i])                {                    in[i] ++;                    if(in[i] >= n) return true;//如果入队次数超过n-1次说明存在环或负权                    Q.push(i);                    vis[i] = true;                }            }        }    }    return false;}
   

转载地址：http://jysgi.baihongyu.com/