学步园

本文转自http://blog.csdn.net/p569354158/article/details/7379778

#define V 9     /*顶点数*/
#define E 12     /*边数*/

const int inf = 0x3f3f3f3f;
int n,m,pre[V];

struct Edge
{
    int u;
    int v;
    int w;
};
Edge edge[E];   /*边表*/
int dist[V];

/**
 * 松弛函数
 */
int relax(int u,int v,int c)
{
    if (dist[v] > dist[u] + c)
    {
        dist[v] = dist[u] + c;
        pre[v] = u;
        return 1;
    }
    return 0;
}
/**
 * 数据初始化
 */
void init_single_source()
{
    for (int i = 0;i < n,i++)
    {
        dist[i] = inf;
        pre[i] = -1;
    }
    return;
}
int bellman(int src)
{
    init_single_source();
    dist[src] = 0;
    bool flag;

    for (int i = 0;i < n;i++)
    {
        flag = false;
        for (int j = 0;j < m;j++)
        {
            if (1 == relax(edge[j].u,edge[j].v,edge[j].w))
            {
                flag = true;
            }
        }
        if (flag == false)
        {
            break;
        }
    }
    /**
     * 对负权回路进行检查
     */
    for (int j = 0;j < m;j++)
    {
        if (1 == relax(edge[j].u,edge[j].v,edge[j].w))
        {
            return 0;
        }
    }
    return 1;
}