資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究單源最短路徑（任意權重）
單源最短路徑演算法（用於任意權重，正或負）也稱為 Bellman-Ford 演算法，用於查詢從源頂點到任何其他頂點的最小距離。該演算法與 Dijkstra 演算法的主要區別在於，在 Dijkstra 演算法中，我們無法處理負權重，但在這裡我們可以輕鬆處理。
Bellman-Ford 演算法以自底向上的方式查詢距離。首先，它查詢路徑中只有一條邊的距離。之後增加路徑長度以查詢所有可能的解。
輸入 − 圖的成本矩陣
0 6 ∞ 7 ∞ ∞ 0 5 8 -4 ∞ -2 0 ∞ ∞ ∞ ∞ -3 0 9 2 ∞ 7 ∞ 0
輸出 − 源頂點：2
頂點：0 1 2 3 4
距離：-4 -2 0 3 -6
前驅：4 2 -1 0 1
該圖沒有負邊迴圈
演算法
bellmanFord(dist, pred, source)
輸入 − 距離列表、前驅列表和源頂點。
輸出 − 當找到負迴圈時，返回 True。
Begin iCount := 1 maxEdge := n * (n - 1) / 2 //n is number of vertices for all vertices v of the graph, do dist[v] := ∞ pred[v] := ϕ done dist[source] := 0 eCount := number of edges present in the graph create edge list named edgeList while iCount < n, do for i := 0 to eCount, do if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i) dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i) pred[edgeList[i].v] := edgeList[i].u done done iCount := iCount + 1 for all vertices i in the graph, do if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i), then return true done return false End
示例 (C++)
#include<iostream>
#include<iomanip>
#define V 5
#define INF 999
using namespace std;
//Cost matrix of the graph (directed) vertex 5
int costMat[V][V] = {
{0, 6, INF, 7, INF},
{INF, 0, 5, 8, -4},
{INF, -2, 0, INF, INF},
{INF, INF, -3, 0, 9},
{2, INF, 7, INF, 0}
};
typedef struct{
int u, v, cost;
}edge;
int isDiagraph(){
//check the graph is directed graph or not
int i, j;
for(i = 0; i<V; i++){
for(j = 0; j<V; j++){
if(costMat[i][j] != costMat[j][i]){
return 1;//graph is directed
}
}
}
return 0;//graph is undirected
}
int makeEdgeList(edge *eList){
//create edgelist from the edges of graph
int count = -1;
if(isDiagraph()){
for(int i = 0; i<V; i++){
for(int j = 0; j<V; j++){
if(costMat[i][j] != 0 && costMat[i][j] != INF){
count++;//edge find when graph is directed
eList[count].u = i; eList[count].v = j;
eList[count].cost = costMat[i][j];
}
}
}
}else{
for(int i = 0; i<V; i++){
for(int j = 0; j<i; j++){
if(costMat[i][j] != INF){
count++;//edge find when graph is undirected
eList[count].u = i; eList[count].v = j;
eList[count].cost = costMat[i][j];
}
}
}
}
return count+1;
}
int bellmanFord(int *dist, int *pred,int src){
int icount = 1, ecount, max = V*(V-1)/2;
edge edgeList[max];
for(int i = 0; i<V; i++){
dist[i] = INF;//initialize with infinity
pred[i] = -1;//no predecessor found.
}
dist[src] = 0;//for starting vertex, distance is 0
ecount = makeEdgeList(edgeList); //edgeList formation
while(icount < V){ //number of iteration is (Vertex - 1)
for(int i = 0; i<ecount; i++){
if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]){
//relax edge and set predecessor
dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v];
pred[edgeList[i].v] = edgeList[i].u;
}
}
icount++;
}
//test for negative cycle
for(int i = 0; i<ecount; i++){
if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]){
return 1;//indicates the graph has negative cycle
}
}
return 0;//no negative cycle
}
void display(int *dist, int *pred){
cout << "Vert: ";
for(int i = 0; i<V; i++)
cout <<setw(3) << i << " ";
cout << endl;
cout << "Dist: ";
for(int i = 0; i<V; i++)
cout << setw(3) << dist[i] << " ";
cout << endl;
cout << "Pred: ";
for(int i = 0; i<V; i++)
cout << setw(3) << pred[i] << " ";
cout << endl;
}
int main(){
int dist[V], pred[V], source, report;
source = 2;
report = bellmanFord(dist, pred, source);
cout << "Source Vertex: " << source<<endl;
display(dist, pred);
if(report)
cout << "The graph has a negative edge cycle" << endl;
else
cout << "The graph has no negative edge cycle" << endl;
}輸出
Source Vertex: 2 Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 The graph has no negative edge cycle
更新於：2020年7月2日
9K+ 次檢視
廣告