# 贝尔曼-福特算法

（重定向自SPFA算法

分类 单源最短路径问题（针对带权有向图） 图 ${\displaystyle O(|V||E|)}$ ${\displaystyle O(|V|)}$

## 算法

### 伪代码表示

procedure BellmanFord(list vertices, list edges, vertex source)
// 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息

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

// 步骤2：重复对每一条边进行松弛操作
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

// 步骤3：检查负权环
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 }


v1 v2 v3 v4
D/P D/P D/P D/P