Bellman Ford's Algorithm

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

1. Algorithms L18.1
LECTURE 18
Shortest Paths II
•Bellman-Ford algorithm
•Linear programming and
difference constraints
•VLSI layout compaction
Algorithms

2. Algorithms L18.2
Negative-weight cycles
Recall: If a graph G = (V, E) contains a negative-
weight cycle, then some shortest paths may not
exist.
Example:
uu vv
…
< 0

3. Algorithms L18.3
Negative-weight cycles
Recall: If a graph G = (V, E) contains a negative-
weight cycle, then some shortest paths may not
exist.
Example:
uu vv
…
< 0
Bellman-Ford algorithm: Finds all shortest-path
lengths from a source s Î V to all v Î V or
determines that a negative-weight cycle exists.

4. Algorithms L18.4
Bellman-Ford algorithm
d[s] ¬ 0
for each v Î V – {s}
do d[v] ¬ ¥
for i ¬ 1 to | V | – 1
do for each edge (u, v) Î E
do if d[v] > d[u] + w(u, v)
then d[v] ¬ d[u] + w(u, v)
for each edge (u, v) Î E
do if d[v] > d[u] + w(u, v)
then report that a negative-weight cycle exists
initialization
At the end, d[v] = d(s, v), if no negative-weight cycles.
Time = O(V E).
relaxation
step

5. Algorithms L18.5
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3

6. Algorithms L18.6
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
¥
0 ¥
¥ ¥
Initialization.

7. Algorithms L18.7
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
¥
0 ¥
¥ ¥
1
2
3
4
5
7
8
Order of edge relaxation.
6

8. Algorithms L18.8
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
¥
0 ¥
¥ ¥
1
2
3
4
5
7
8
6

9. Algorithms L18.9
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
¥
0 ¥
¥ ¥
1
2
3
4
5
7
8
6

10. Algorithms L18.10
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
¥
0 ¥
¥ ¥
1
2
3
4
5
7
8
6

11. Algorithms L18.11
¥-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0 ¥
¥ ¥
1
2
3
4
5
7
8
6

12. Algorithms L18.12
¥4
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0 ¥
¥
1
2
3
4
5
7
8
6

13. Algorithms L18.13
4
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0 ¥
¥
1
2
3
4
5
7
8
6

14. Algorithms L18.14
42
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0 ¥
¥
1
2
3
4
5
7
8
6

15. Algorithms L18.15
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0 ¥
¥
1
2
3
4
5
7
8
6

16. Algorithms L18.16
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0 ¥
¥
1
2
3
4
5
7
8
End of pass 1.
6

17. Algorithms L18.17
¥1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
¥
1
2
3
4
5
7
8
6

18. Algorithms L18.18
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
¥
1
2
3
4
5
7
8
6

19. Algorithms L18.19
¥1
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
1
2
3
4
5
7
8
6

20. Algorithms L18.20
1
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
1
2
3
4
5
7
8
6

21. Algorithms L18.21
1
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
1
2
3
4
5
7
8
6

22. Algorithms L18.22
1
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
1
2
3
4
5
7
8
6

23. Algorithms L18.23
1
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
1
2
3
4
5
7
8
6

24. Algorithms L18.24
1-2
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
1
2
3
4
5
7
8
6

25. Algorithms L18.25
-2
1
2
-1
Example of Bellman-Ford
AA
BB
EE
CC DD
–1
4
1
2
–3
2
5
3
0
1
2
3
4
5
7
8
6
End of pass 2 (and 3 and 4).

26. Algorithms L18.26
Correctness
Theorem. If G = (V, E) contains no negative-
weight cycles, then after the Bellman-Ford
algorithm executes, d[v] = d(s, v) for all v Î V.

27. Algorithms L18.27
Correctness
Theorem. If G = (V, E) contains no negative-
weight cycles, then after the Bellman-Ford
algorithm executes, d[v] = d(s, v) for all v Î V.
Proof. Let v Î V be any vertex, and consider a shortest
path p from s to v with the minimum number of edges.
v
1
v
1
v
2
v
2
v
3
v
3 v
k
v
k
v
0
v
0
…
s
v
p:
Since p is a shortest path, we have
d(s, v
i
) = d(s, v
i–1
) + w(v
i–1
, v
i
) .

28. Algorithms L18.28
Correctness (continued)
v
1
v
1
v
2
v
2
v
3
v
3 v
k
v
k
v
0
v
0
…
s
v
p:
Initially, d[v
0
] = 0 = d(s, v
0
), and d[v
0
] is unchanged by
subsequent relaxations (because of the lemma from
Lecture 14 that d[v] ³ d(s, v)).
•After 1 pass through E, we have d[v
1
] = d(s, v
1
).
•After 2 passes through E, we have d[v
2
] = d(s, v
2
).

•After k passes through E, we have d[v
k
] = d(s, v
k
).
Since G contains no negative-weight cycles, p is simple.
Longest simple path has £ | V | – 1 edges.

29. Algorithms L18.29
Detection of negative-weight
cycles
Corollary. If a value d[v] fails to converge after
| V | – 1 passes, there exists a negative-weight
cycle in G reachable from s.

30. Algorithms L18.30
Linear programming
Let A be an m´n matrix, b be an m-vector, and c
be an n-vector. Find an n-vector x that maximizes
c
T
x subject to Ax £ b, or determine that no such
solution exists.
.£
.
maximizingm
n
A x£b c
T
x

31. Algorithms L18.31
Linear-programming
algorithms
Algorithms for the general problem
•Simplex methods — practical, but worst-case
exponential time.
•Interior-point methods — polynomial time and
competes with simplex.

32. Algorithms L18.32
Linear-programming
algorithms
Algorithms for the general problem
•Simplex methods — practical, but worst-case
exponential time.
•Interior-point methods — polynomial time and
competes with simplex.
Feasibility problem: No optimization criterion.
Just find x such that Ax £ b.
• In general, just as hard as ordinary LP.

33. Algorithms L18.33
Solving a system of difference
constraints
Linear programming where each row of A contains
exactly one 1, one –1, and the rest 0’s.
Example:
x
1
– x
2
£ 3
x
2
– x
3
£ –2
x
1 – x
3 £ 2
x
j
– x
i
£ w
ij

34. Algorithms L18.34
Solving a system of difference
constraints
Linear programming where each row of A contains
exactly one 1, one –1, and the rest 0’s.
Example:
x
1
– x
2
£ 3
x
2
– x
3
£ –2
x
1 – x
3 £ 2
x
j
– x
i
£ w
ij
Solution:
x
1
= 3
x
2
= 0
x
3 = 2

35. Algorithms L18.35
Solving a system of difference
constraints
Linear programming where each row of A contains
exactly one 1, one –1, and the rest 0’s.
Example:
x
1
– x
2
£ 3
x
2
– x
3
£ –2
x
1 – x
3 £ 2
x
j
– x
i
£ w
ij
Solution:
x
1
= 3
x
2
= 0
x
3 = 2
Constraint graph:
v
j
v
jv
i
v
ix
j
– x
i
£ w
ij
w
ij
(The “A”
matrix has
dimensions
|E | ´ |V |.)

36. Algorithms L18.36
Unsatisfiable constraints
Theorem. If the constraint graph contains
a negative-weight cycle, then the system of
differences is unsatisfiable.

37. Algorithms L18.37
Unsatisfiable constraints
Theorem. If the constraint graph contains
a negative-weight cycle, then the system of
differences is unsatisfiable.
Proof. Suppose that the negative-weight cycle is
v
1
® v
2
®  ® v
k
® v
1
. Then, we have
x
2
–x
1
£ w
12
x
3
–x
2
£ w
23

x
k
–x
k–1
£ w
k–1, k
x
1
–x
k
£ w
k1

38. Algorithms L18.38
Unsatisfiable constraints
Theorem. If the constraint graph contains
a negative-weight cycle, then the system of
differences is unsatisfiable.
Proof. Suppose that the negative-weight cycle is
v
1
® v
2
®  ® v
k
® v
1
. Then, we have
x
2
–x
1
£ w
12
x
3
–x
2
£ w
23

x
k
–x
k–1
£ w
k–1, k
x
1
–x
k
£ w
k1
Therefore, no
values for the x
i

can satisfy the
constraints.
0 £ weight of cycle
< 0

39. Algorithms L18.39
Satisfying the constraints
Theorem. Suppose no negative-weight cycle
exists in the constraint graph. Then, the
constraints are satisfiable.

40. Algorithms L18.40
Satisfying the constraints
Theorem. Suppose no negative-weight cycle
exists in the constraint graph. Then, the
constraints are satisfiable.
Proof. Add a new vertex s to V with a 0-weight edge
to each vertex v
i
Î V.
v
1
v
1
v
4
v
4
v
7
v
7
v
9
v
9
v
3
v
3

41. Algorithms L18.41
Satisfying the constraints
Theorem. Suppose no negative-weight cycle
exists in the constraint graph. Then, the
constraints are satisfiable.
Proof. Add a new vertex s to V with a 0-weight edge
to each vertex v
i
Î V.
v
1
v
1
v
4
v
4
v
7
v
7
v
9
v
9
v
3
v
3
s
0 Note:
No negative-weight
cycles introduced Þ
shortest paths exist.

42. Algorithms L18.42
The triangle inequality gives us d(s,v
j
) £ d(s, v
i
) + w
ij
.
Since x
i
= d(s, v
i
) and x
j
= d(s, v
j
), the constraint x
j
– x
i

£ w
ij
is satisfied.
Proof (continued)
Claim: The assignment x
i
= d(s, v
i
) solves the constraints.
ss
v
j
v
j
v
i
v
i
d(s, v
i
)
d(s, v
j
)
w
ij
Consider any constraint x
j
– x
i
£ w
ij
, and consider the
shortest paths from s to v
j
and v
i
:

43. Algorithms L18.43
Bellman-Ford and linear
programming
Corollary. The Bellman-Ford algorithm can
solve a system of m difference constraints on n
variables in O(m n) time.
Single-source shortest paths is a simple LP
problem.
In fact, Bellman-Ford maximizes x
1
+ x
2
+  + x
n
subject to the constraints x
j
– x
i
£ w
ij
and x
i
£ 0
(exercise).
Bellman-Ford also minimizes max
i
{x
i} – min
i
{x
i}
(exercise).

44. Algorithms L18.44
Application to VLSI layout
compaction
Integrated
-circuit
features:
Problem: Compact (in one dimension) the
space between the features of a VLSI layout
without bringing any features too close together.
minimum separation l

45. Algorithms L18.45
VLSI layout compaction
11
x
1
x
2
2
d
1
Constraint:x
2
– x
1
³ d
1
+ l
Bellman-Ford minimizes max
i
{x
i} – min
i
{x
i},
which compacts the layout in the x-dimension.