Shortest Paths II: Bellman-Ford, Topological Sort, DAG Shortest Paths, Linear Programming, Difference Constraints

Shortest Paths II: BellmanFord, Topological Sort, DAG
Shortest Paths, Linear

Programming, Difference
Constraints
Lecture 15
Negative-weight cycles
Recall: If a graph G = (V, E) contains a negativeweight cycle, then some shortest paths may not exist.
Example:
<0
u
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.
L15.2
Bellman-Ford algorithm
d[s] 0
for each v V {s}
do d[v]
initialization
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)
relaxation
step
for each edge (u, v) E

do if d[v] > d[u] + w(u, v)
then report that a negative-weight cycle exists
At the end, d[v] = d(s, v). Time = O(V E).

L15.3
Example of Bellman-Ford
A
4
A B C D E
0
E
3
L15.4
1
B
A
4
A B C D E
0
0 1
E
3
L15.5
1
B
A
4
A
0
0
0
1
1
C
4
L15.6
1
B
A
4
E
3
C
42
A
0
0
0
0
1
1
1
4
2
L15.7
1
B
A
4
E
3
C
2
A
0
0
0
0
1
1
1
4
2
L15.8
1
B
A
4
E
3
C
2
A
0
0
0
0
0
1
1
1
1
4
2
2
L15.9
1
B
A
4
E
3
C
2
A
0
0
0
0
0
0
1
1
1
1
1
4
2
2
2
1
1
L15.10
1
B
A
4
E
3
C
2
D
2
1
A
0
0
0
0
0
0
0
1
1
1
1
1
1
4
2
2
2
2
1
2
1
1
1
L15.11
1
B
A
4
E
3
C 5 D
2
2
1
Note: Values decrease
monotonically.
A
0
0
0
0
0
0
0
1
1
1
1
1
1
4
2
2
2
2
1
2
1
1
1
L15.12
Correctness
Theorem. If G = (V, E) contains no negativeweight 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.
p: v0
v
v
k
Since p is a shortest path, we have

d(s, vi) = d(s, vi1) + w(vi1, vi) .
L15.13
Correctness (continued)
s
p: v0
v
v
k
Initially, d[v0] = 0 = d(s, v0), and d[s] is unchanged by

subsequent relaxations (because of the lemma from
Lecture 17 that d[v] d(s, v)).
After 1 pass through E, we have d[v1] = d(s, v1).
After 2 passes through E, we have d[v2] = d(s, v2).
M
After k passes through E, we have d[vk] = d(s, vk).
Since G contains no negative-weight cycles, p is simple.
Longest simple path has | V | 1 edges.
L15.14
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.
L15.15
DAG shortest paths

If the graph is a directed acyclic graph (DAG), we first
topologically sort the vertices.
Determine f : V {1, 2, , | V |} such that (u, v) E
f (u) < f (v).
O(V + E) time using depth-first search.
4
3
s 2
7
6
8
9
Walk through the vertices u V in this order, relaxing

the edges in Adj[u], thereby obtaining the shortest paths
from s in a total of O(V + E) time.
L15.16
Linear programming
Let A be an mn matrix, b be an m-vector, and c
be an n-vector. Find an n-vector x that maximizes
cTx subject to Ax b, or determine that no such
solution exists.
n
m
x b
maximizing
cT
x
L15.17
Linear-programming
algorithms
Algorithms for the general problem
Simplex methods practical, but worst-case
exponential time.
Ellipsoid algorithm polynomial time, but
slow in practice.
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.
L15.18
Solving a system of difference

constraints
Linear programming where each row of A contains
exactly one 1, one 1, and the rest 0s.
Solution:
Example:
x1 = 3
x 1 x2 3
x2 = 0
xj xi wij
x2 x3 2
x3 = 2
x 1 x3 2
Constraint graph:
xj xi wij
vi
wij
vj
(The A
matrix has
dimensions
|E | |V |.)
L15.19
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
v1 v2 L vk v1. Then, we have
x2 x1
x3 x2
w12
w23
M
xk xk1 wk1, k
x1 xk wk1
0
weight of cycle
<0
Therefore, no
values for the xi
can satisfy the
constraints.
L15.20
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 vi V.
0
s
Note:
No negative-weight
cycles introduced
shortest paths exist.
L15.21
Proof (continued)
Claim: The assignment xi = d(s, vi) solves the constraints.
Consider any constraint xj xi wij, and consider the
shortest paths from s to vj and vi:
d(s, vi)
vi
d(s, vj)
wij
vj
The triangle inequality gives us d(s,vj) d(s, vi) + wij.
Since xi = d(s, vi) and xj = d(s, vj), the constraint xj xi
wij is satisfied.
L15.22
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 x1 + x2 + L + xn
subject to the constraints xj xi wij and xi 0
(exercise).
Bellman-Ford also minimizes maxi{xi} mini{xi}
(exercise).
L15.23

Shortest Paths II: Bellman-Ford, Topological Sort, DAG Shortest Paths, Linear Programming, Difference Constraints

Uploaded by

Copyright:

Available Formats

Shortest Paths II: Bellman-Ford, Topological Sort, DAG Shortest Paths, Linear Programming, Difference Constraints

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Shortest Paths II: Bellman-Ford, Topological Sort, DAG Shortest Paths, Linear Programming, Difference Constraints

Uploaded by

Copyright:

Available Formats

Shortest Paths II: BellmanFord, Topological Sort, DAG

Shortest Paths, Linear

Bellman-Ford algorithm: Finds all shortest-path

for each edge (u, v) E

At the end, d[v] = d(s, v). Time = O(V E).

Since p is a shortest path, we have

Initially, d[v0] = 0 = d(s, v0), and d[s] is unchanged by

DAG shortest paths

Walk through the vertices u V in this order, relaxing

Feasibility problem: No optimization criterion.

Solving a system of difference

Satisfying the constraints

Bellman-Ford and linear

You might also like