# 贝尔曼-福特算法

（重定向自Bellman-Ford算法

## 算法

### pseudocode

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语言示例

 1 Begin
2   initialize-single-source(G,s);
3   initialize-queue(Q);
4   enqueue(Q,s);
5   while not empty(Q) do
6     begin
7       u:=dequeue(Q);
9         begin
10           tmp:=d[v];
11           relax(u,v);
12           if (tmp<>d[v]) and (not v in Q) then
13             enqueue(Q,v);
14         end;
15     end;
16 End;


C++语言示例

 1 int SPFA(int s) {
2 	queue<int> q;
3 	bool inq[maxn] = {false};
4 	for(int i = 1; i <= N; i++) dis[i] = 2147483647;
5 	dis[s] = 0;
6 	q.push(s); inq[s] = true;
7 	while(!q.empty()) {
8 		int x = q.front(); q.pop();
9 		inq[x] = false;
10 		for(int i = front[x]; i !=0 ; i = e[i].next) {
11 			int k = e[i].v;
12 			if(dis[k] > dis[x] + e[i].w) {
13 				dis[k] = dis[x] + e[i].w;
14 				if(!inq[k]) {
15 					inq[k] = true;
16 					q.push(k);
17 				}
18 			}
19 		}
20 	}
21 	for(int i =  1; i <= N; i++) cout << dis[i] << ' ';
22 	cout << endl;
23 	return 0;
24 }


## 样例

${\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})\},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}$