BellmanFord算法

算法

Bellman-Ford(G, w, s)
	for each vertex v 属于 V[G]
		d[v] = 无穷大
		p[v] = NIL
	d[s] = 0

	for i = 1 to |V[G]| - 1
		relax(u, v, w)
	for each edge(u, v)属于E[G]
		if d[v] > d[u] + w(u, v)
			return false
	
	return true
1
2
3
4
5
6
7
8
9
10
11
12
13

实践

UVa11090 Going in Cycle!!