含有负边的图的最短路径（Bellman_ford算法）

更新所有的边，每条边更新V-1次，时间复杂度为O(V*E).

有些更新操作是重复了的，这里可以考虑检查多余的重复操作作，如果没有更新发生，则立即终止算法。

#include<iostream>      

#include<malloc.h>      

#include<queue>    

#include <algorithm>     

#include<stdlib.h>    

#include<functional>  

using namespace std;      

#define maxNum 100 //定义邻接举证的最大定点数    

#define maxWeight 1000000 //边权最大值    

//顶点信息  

typedef struct  

{  

    int id;  

    int dist;  

}node;  

//图的邻接矩阵表示结构      

typedef struct      

{      

    //char v[maxNum];//图的顶点信息   

    node v[maxNum];  

    int e[maxNum][maxNum];//图的顶点信息      

    int vNum;//顶点个数      

    int eNum;//边的个数      

}graph;  

//函数声明    

void createGraph(graph *g);//创建图g   

//Bellman_ford算法  

void Bellman_ford(graph *g)  

    int k,i,j;    

    //初始化dist的值  

    for(i=1;i<=g->vNum;i++)    

    {  

        g->v[i].dist=maxWeight;  //dist为最大值  

        g->v[i].id=i;  

    }  

    g->v[1].dist=0;//1作为源点，dist为0  

    for(k=1;k<=g->vNum;k++)//V-1次循环  

        for(i=1;i<=g->vNum;i++)  

        {  

            for(j=1;j<=g->vNum;j++)  

            {  

                if(g->e[i][j]!=maxWeight)  

                    if(g->v[j].dist>(g->v[i].dist+g->e[i][j]))  

                        g->v[j].dist=g->v[i].dist+g->e[i][j];  

            }  

        }  

        //for(int p=1;p<=g->vNum;p++)//输出每次更新完以后的dist  

        //  cout<<g->v[p].dist<<" ";  

        //cout<<endl;  

}  

void createGraph(graph *g)//创建图g      

    cout<<"正在创建无向图..."<<endl;      

    cout<<"请输入顶点个数vNum:";      

    cin>>g->vNum;       

    int i,j;    

    //构造邻接矩阵，顶点到自身的距离是无穷大的。    

    cout<<"输入邻接矩阵权值："<<endl;   

    for(i=1;i<=g->vNum;i++)  

        for(j=1;j<=g->vNum;j++)  

            cin>>g->e[i][j];  

            if(g->e[i][j]==0)  

                g->e[i][j]=maxWeight;  

}      

int main()      

    graph *g;      

    g=(graph*)malloc(sizeof(graph));      

    createGraph(g);      

    Bellman_ford(g);   

    cout<<"Dijkstra算法单源(源为1)最短路径为："<<endl;  

    for(int k=1; k<=g->vNum; k++)  

        cout<<g->v[k].dist<<" ";  

    cout<<endl;  

    system("pause");    

    return 0;      

/* 

正在创建无向图... 

请输入顶点个数vNum:8 

输入邻接矩阵权值： 

0 10 0 0 0 0 0 8 

0 0 0 0 0 2 0 0 

0 1 0 1 0 0 0 0 

0 0 0 0 3 0 0 0 

0 0 0 0 0 -1 0 0 

0 0 -2 0 0 0 0 0 

0 -4 0 0 0 -1 0 0 

0 0 0 0 0 0 1 0 

Dijkstra算法单源(源为1)最短路径为： 

0 5 5 6 9 7 9 8 

请按任意键继续. . . 

*/  

1.修改：dist单独列出一个数组存放，不在将dist值存放在图中。

2.输出dist修改过程，发现后续的dist没有发生变化，可以通过一个检查函数来判断，如果dist前后没有发生变化则表明已经找到最短路径

代码实例：

int dist[maxNum];//定义数组，默认情况下数组中的所有元素都为0  

    char v[maxNum];//图的顶点信息   

void Bellman_ford(graph *g);  

    int k,i,j,p;    

        dist[i]=maxWeight;  

    dist[1]=0;  

        cout<<dist[i]<<" ";  

    cout<<"输出"<<g->vNum<<"次迭代过程中的dist值"<<endl;  

        //更新每一条边的权值  

                if(g->e[i][j]!=maxWeight&&dist[i]!=maxWeight)//如果i->j之间存在路径  

                {  

                    if(dist[j]>dist[i]+g->e[i][j])  

                    {  

                        dist[j]=dist[i]+g->e[i][j];  

                    }  

                }  

            cout<<dist[i]<<" ";  

        cout<<endl;  

        cout<<dist[k]<<" ";  

0 1000000 1000000 1000000 1000000 1000000 1000000 1000000 

输出8次迭代过程中的dist值 

0 10 10 1000000 1000000 12 9 8 

0 5 10 11 14 8 9 8 

0 5 5 11 14 7 9 8 

本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2011/06/14/2297002.html，如需转载请自行联系原作者