? ? ? Bellman_Ford算法和Dijkstra算法都可以用來求解有向圖的單源最短路徑問題，但是，相比于Dijkstra算法，?Bellman_Ford算法允許邊的權(quán)重為負(fù)值。

?

? ? 算法的詳細(xì)討論見算法導(dǎo)論或者下面這個(gè)博客http://blog.csdn.net/niushuai666/article/details/6791765

?

? 代碼如下：

#include<iostream>using namespace std;#define Inf 65535 #define NotAVerter -1/鄰接鏈表的相關(guān)定義// typedef struct EdgeNode *position; typedef struct Led_table* Table;struct EdgeNode //邊表結(jié)點(diǎn) {int adjvex; // 鄰接點(diǎn)域,存儲(chǔ)該頂點(diǎn)對(duì)應(yīng)的下標(biāo)int weight; // 對(duì)應(yīng)邊的權(quán)值int dis; //此數(shù)據(jù)記錄從源點(diǎn)到該節(jié)點(diǎn)的最短距離int precursor; //此數(shù)據(jù)記錄該節(jié)點(diǎn)在廣度優(yōu)先樹種的前驅(qū)節(jié)點(diǎn)position next; // 鏈域,指向下一個(gè)鄰接點(diǎn) };struct Led_table // 鄰接表結(jié)構(gòu) {int data; //鄰接表的大小position *firstedge; //邊表頭指針，可以理解為數(shù)組 };//鄰接鏈表相關(guān)函數(shù)定義/// Table Creat_Lable(int MaxElements) //MaxElements參數(shù)為希望創(chuàng)建的節(jié)點(diǎn)數(shù) {Table table1 = static_cast<Table> (malloc(sizeof(struct Led_table)));table1->data = MaxElements;if (table1 == NULL){cout << "out of space!!!";}table1->firstedge = static_cast<position*>(malloc(sizeof(position)*(table1->data)));if (table1->firstedge == NULL){cout << "out of space!!!";}//給每個(gè)表頭賦值，從0開始for (int i = 0; i <= table1->data - 1; ++i){table1->firstedge[i] = static_cast<position>(malloc(sizeof(EdgeNode))); //申請(qǐng)一個(gè)節(jié)點(diǎn)if (table1->firstedge[i] == NULL){cout << "out of space!!!";}table1->firstedge[i]->adjvex = 0; //表頭這個(gè)參數(shù)沒有意義table1->firstedge[i]->weight = 0; //表頭這個(gè)參數(shù)沒有意義table1->firstedge[i]->dis = Inf;table1->firstedge[i]->precursor = NotAVerter;table1->firstedge[i]->next = NULL;}return table1;}void Insert(Table table1, int v, int w, int weig) //表示存在一條邊為<v,w> {position p = static_cast<position>(malloc(sizeof(EdgeNode))); //申請(qǐng)一個(gè)節(jié)點(diǎn)if (p == NULL){cout << "out of space!!!";}p->adjvex = w;p->weight = weig; //對(duì)于無權(quán)圖來說，該域可以設(shè)置為1p->dis = Inf; //對(duì)于普通節(jié)點(diǎn)來說無意義p->precursor = NotAVerter; //對(duì)于普通節(jié)點(diǎn)來說無意義p->next = table1->firstedge[v]->next;table1->firstedge[v]->next = p;}void init_yuandian(Table table1, int s) //把s設(shè)置為圖的源點(diǎn) {table1->firstedge[s]->adjvex = 0;table1->firstedge[s]->weight = 0;table1->firstedge[s]->dis = 0; //源點(diǎn)的這個(gè)值設(shè)置為0table1->firstedge[s]->precursor = NotAVerter; }bool Bellman_Ford(Table table1, int s) {for (int i = 1; i <= table1->data - 1; ++i) //每條邊進(jìn)行N-1次松弛操作{for (int j = 0; j <= table1->data - 1; ++j) //對(duì)每條邊{position p = table1->firstedge[j]->next;while (p != NULL){if (table1->firstedge[p->adjvex]->dis > table1->firstedge[j]->dis + p->weight) //松弛操作{table1->firstedge[p->adjvex]->dis = table1->firstedge[j]->dis + p->weight;table1->firstedge[p->adjvex]->precursor = j;}p = p->next;}}}bool flag = true;for (int j = 0; j <= table1->data - 1; ++j) //對(duì)每條邊{position p = table1->firstedge[j]->next;while (p != NULL){if (table1->firstedge[p->adjvex]->dis > table1->firstedge[j]->dis + p->weight){flag = false;break;}p = p->next;}}return flag; }void print_path(Table table1, int v) {if (table1->firstedge[v]->precursor != NotAVerter)print_path(table1, table1->firstedge[v]->precursor);cout << "v" << v << endl; }int main() {Table table_1 = Creat_Lable(5); //創(chuàng)建一個(gè)大小為5的鄰接表Insert(table_1, 0, 1, 6); Insert(table_1, 0, 3, 7);Insert(table_1, 1, 2, 5); Insert(table_1, 1, 3, 8); Insert(table_1, 1, 4, -4);Insert(table_1, 2, 1, -2);Insert(table_1, 3, 2, -3); Insert(table_1, 3, 4, 9);Insert(table_1, 4, 0, 2); Insert(table_1, 4, 2, 7); init_yuandian(table_1, 0); //把0設(shè)置為圖的源點(diǎn)cout << Bellman_Ford(table_1, 0) << endl;cout << table_1->firstedge[4]->dis << endl;print_path(table_1, 4);return 0; }

　　夜深了，夜更深了

轉(zhuǎn)載于:https://www.cnblogs.com/1242118789lr/p/7648011.html

總結(jié)

以上是生活随笔為你收集整理的Bellman_Ford算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。