更新所有的邊，每條邊更新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 請按任意鍵繼續. . . */?

?

?

ps:2011-6-15

1.修改：dist單獨列出一個數組存放，不在將dist值存放在圖中。

2.輸出dist修改過程，發現后續的dist沒有發生變化，可以通過一個檢查函數來判斷，如果dist前后沒有發生變化則表明已經找到最短路徑

代碼實例：

#include<iostream> #include<malloc.h> #include<queue> #include <algorithm> #include<stdlib.h> #include<functional> using namespace std; #define maxNum 100 //定義鄰接舉證的最大定點數 #define maxWeight 1000000 //邊權最大值 int dist[maxNum];//定義數組，默認情況下數組中的所有元素都為0 //圖的鄰接矩陣表示結構 typedef struct { char v[maxNum];//圖的頂點信息 int e[maxNum][maxNum];//圖的頂點信息 int vNum;//頂點個數 int eNum;//邊的個數 }graph; //函數聲明 void createGraph(graph *g);//創建圖g void Bellman_ford(graph *g); //Bellman_ford算法 void Bellman_ford(graph *g) { int k,i,j,p; //初始化dist的值 for(i=1;i<=g->vNum;i++) { dist[i]=maxWeight; } dist[1]=0; for(i=1;i<=g->vNum;i++) { cout<<dist[i]<<" "; } cout<<endl; cout<<"輸出"<<g->vNum<<"次迭代過程中的dist值"<<endl; 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&&dist[i]!=maxWeight)//如果i->j之間存在路徑 { if(dist[j]>dist[i]+g->e[i][j]) { dist[j]=dist[i]+g->e[i][j]; } } } } for(i=1;i<=g->vNum;i++) { cout<<dist[i]<<" "; } 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<<dist[k]<<" "; } 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 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 0 5 5 6 9 7 9 8 0 5 5 6 9 7 9 8 0 5 5 6 9 7 9 8 0 5 5 6 9 7 9 8 0 5 5 6 9 7 9 8 Dijkstra算法單源(源為1)最短路徑為： 0 5 5 6 9 7 9 8 請按任意鍵繼續. . . */?

?

轉載于:https://www.cnblogs.com/xwdreamer/archive/2011/06/14/2297002.html

總結

以上是生活随笔為你收集整理的含有负边的图的最短路径（Bellman_ford算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。