bellman_ford.cpp

来自「图论的一些常用代码」· C++ 代码 · 共 35 行

/*
 *功能：单源最短路径，可以有负权边，邻接阵表示
 *参数：传入图的大:n mat:邻接阵 s:源点 min:各点最短距离 pre:路径-记录s到i上的父结点，pre[s]=-1
 *返回：min pre，若含有负边环则求解失败，返回0
 *优化：先删除负边使用dijkstra求出上界，加快迭代过程
 */
#define MAXN 200
#define inf 1000000000
typedef int elem_t;
int bellman_ford(int n,elem_t mat[][MAXN],int s,elem_t * min,int * pre)
{
    int v[MAXN],i,j,k,tag;
    for (i=0;i<n;i++)
        min[i]=inf,v[i]=0,pre[i]=-1;
    for (min[s]=0,j=0;j<n;j++)
    {
        for (k=-1,i=0;i<n;i++)
            if (!v[i] && (k==-1)||min[i]<min[k])
                k=i;
        for (v[k]=1,i=0;i<n;i++)
            if (!v[i] && mat[k][i]>=0 && min[k]+mat[k][i]<min[i])
                min[i]=min[k]+mat[pre[i]=k][i];
    }
    for (tag=1,j=0;tag &&j<=n;j++)
    {
        for (tag=i=0;i<n;i++)
        {
            for (k=0;k<n;k++)
                if (min[k]+mat[k][i]<min[i])
                    min[i]=min[k]+mat[pre[i]=k][i],tag=1;
        }
    }
    return j<=n;
}