欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Flody板子及其各类优化:Flody + 路径输出 ,Bellman-Ford,Bellman-Ford + 队列优化 + 前向星

程序员文章站 2022-05-12 15:02:11
...
void Flody()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(G[i][j]>G[i][k]+G[k][j])
                {
                    G[i][j]=G[i][k]+G[k][j];
                }
            }
        }
    }
}
//Flody + 路径输出

//初始化,两点间无道路,e[i][j]初始化为正无穷
//	如果两点间有道路,记录每点的后驱 path[i][j] = j;

void flody()
{
    For(k,1,N)
    {
        For(i,1,N)
        {
            For(j,1,N)
            {
                if(e[i][j] == e[i][k] + e[k][j])
                {
                    if(path[i][j] > path[i][k])//找到字典序最小的路path[i][j] = path[i][k];
                }
                if(e[i][j] > e[i][k] + e[k][j])
                {
                    e[i][j] = e[i][k] + e[k][j];
                    path[i][j] = path[i][k];
                }
            }
        }
    }
}

//Bellman-Ford

//存图
int tot;
struct Node
{
    int u, v, w;
} e[4005];
void add(int u, int v, int w)
{
    e[tot].u = u;
    e[tot].v = v;
    e[tot++].w = w;
}
int dis[1005];
int Bellman_Ford(int u, int En)
{
    memset(dis,0x3f,sizeof(dis));
    dis[u] = 0;
    For(i,2,N)
    {
        int check = 1;
        For(j,0,tot)//遍历所有边
        {
            if(dis[ e[j].v ] > dis[ e[j].u ] + e[j].w)
            {
                dis[ e[j].v ] = dis[ e[j].u ] + e[j].w;
                check = 0;
            }
        }
        if(check) break;
    }
    For(j,0,tot)//判断 有无负环
    {
        if(dis[ e[j].v ] > dis[ e[j].u ] + e[j].w) return -1;//存在负环
    }
    int main()
    {
        tot = 0;
        while(M--)	//路径数
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);	//单向边
        }
        printf("%d\n",Bellman_Ford(1,N));
        return 0;
    }

//Bellman-Ford + 队列优化 + 前向星

//存图使用前向星

int dis[1005], cnt[1005];
bool book[1005];

int spfa(int u, int En)
{
    memset(book,false,sizeof(book));
    memset(cnt,0,sizeof(cnt));
    memset(dis,0x3f,sizeof(dis));
    book[u] = 1;
    cnt[u] = 1;
    dis[u] = 0;

    queue<int> q;
    q.push(u);
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        book[u] = 0;
        for(int i = first[u]; ~i; i = e[i].next)
        {
            if(dis[ e[i].v ] > dis[u] + e[i].w)
            {
                dis[ e[i].v ] = dis[u] + e[i].w;

                if(!book[ e[i].v ])
                {
                    q.push(e[i].v);
                    book[e[i].v] = 1;
                    cnt[ e[i].v ]++;
                    if(cnt[ e[i].v ] > N) return -1; //存在负环
                }
            }
        }
    }
    return dis[En];
}

 

相关标签: 板子