# 贝尔曼-福特算法

## 算法

### 偽代碼

procedure BellmanFord(list vertices, list edges, vertex source)
// 讀入邊和節點的列表並對distance和predecessor寫入最短路徑

// 初始化圖
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null

// 對每一條邊重複操作
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u

// 檢查是否有負權重的回路
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "圖包含負權重的回路"


## 优化

### 队列优化

Pascal语言示例

Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do
begin
u:=dequeue(Q);
begin
tmp:=d[v];
relax(u,v);
if (tmp<>d[v]) and (not v in Q) then
enqueue(Q,v);
end;
end;
End;


C++语言示例

int SPFA(int s) {
std::queue<int> q;
bool inq[maxn] = {false};
for(int i = 1; i <= N; i++) dis[i] = 2147483647;
dis[s] = 0;
q.push(s); inq[s] = true;
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = false;
for(int i = front[x]; i !=0 ; i = e[i].next) {
int k = e[i].v;
if(dis[k] > dis[x] + e[i].w) {
dis[k] = dis[x] + e[i].w;
if(!inq[k]) {
inq[k] = true;
q.push(k);
}
}
}
}
for(int i =  1; i <= N; i++) std::cout << dis[i] << ' ';
std::cout << std::endl;
return 0;
}


## 样例

${\displaystyle V=\{v_{1},v_{2},v_{3},v_{4}\},E=\{(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{4}),(v_{4},v_{3})\))$${\displaystyle weight(v_{1},v_{2})=-1,weight(v_{1},v_{3})=3,weight(v_{2},v_{4})=3,weight(v_{4},v_{3})=-1}$

${\displaystyle v_{1))$ ${\displaystyle v_{2))$ ${\displaystyle v_{3))$ ${\displaystyle v_{4))$
${\displaystyle D/P}$ ${\displaystyle D/P}$ ${\displaystyle D/P}$ ${\displaystyle D/P}$

## 参考文献

1. ^ 存档副本. [2013-07-17]. （原始内容存档于2016-03-04）.