含有負邊的圖的最短路徑（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，如需轉載請自行聯系原作者