Negative Cycle Detection

Algorithmique
Fall semester 2011/12
 Recap

Given: Directed+connected graph G with edge weights w(e) on edges e.

Definition: A negative cycle in G is a cycle v0 − v1 − · · · − vt − v0
in which w(v0 , v1 ) + w(v1 , v2 ) + · · · + w(vt , v0 ) < 0
Goal: Determine whether the graph has a negative cycle.

2 3 6

4
-2 2
1 -3 Cycle value = -2-2+2=-2 < 0
4 7
3

-2
3 2 4
5 2
1 -2
4
8
 Moore-Bellman-Ford Algorithm

Assumes: n nodes, set of edges E, set of nodes V, s in V, no negative cycles

Finds: for all nodes v, the shortest path from s to v
How: for every node v, keep track of a value l(v) and pred(v); l(v) is the current estimate of the
length of shortest path to v, pred(v) is the predecessor of v in this shortest path

(1) dist(s) = 0, dist(v) = infinity if v is not s, pred(v) = NULL for all v

(2) For i from 1 to n-1 do
(A) For all edges (u,v) in E do Invariant:
at iteration i, l(v) is the length of the
shortest path from s to v using at most i
(a) if ( l(u) + w(u,v) < l(v) ) then edges.

(i) Set l(v) to l(u) + w(u,v)

(ii) Set pred(v) to u
 Example

-1 -2

1 3 2 5 -2 6

1
4 -4
4

Nodes

1 2 3 4 5 6
0 0 inf inf inf inf inf Initialization

1 0 3 inf inf inf inf

Iterations 2 0 3 2 inf inf inf
3 0 3 2 inf 0 inf
4 0 3 2 1 0 -2
5 0 3 2 1 0 -3

=min( inf-4, 0-2)=-2

 Example

-1 -2

1 3 2 5 -2 6

1
4 -4
4

Nodes

1 2 3 4 5 6
0 0 inf inf inf inf inf Initialization

1 0 3 inf inf inf inf

Iterations 2 0 3 2 inf inf inf

3 0 3 2 inf 0 inf
4 0 3 2 1 0 -2
5 0 3 2 1 0 -3
6 0 3 2 1 0 -3 Stays the same in the next iteration
 Why does it work?

Invariant:
• l(v) is the length of the shortest path from s to v using at most i edges in the i-th iteration.
At most i edges
• Proof by induction.

v
s

Less than i edges

Negative cycles: If there are no negative cycles visible from s, then for any v there is a
shortest path from s to v using at most n-1 edges. A negative cycle visible from s is a negative cycle on a path
from s to some other node v in the graph.

If there is a path with n or more edges, then there

is a cycle, and it can be removed.
Cycle can be removed
since not negative
 Visible Negative Cycles

If the l-value of at least one node changes in round n of the MBF algorithm, then there is a
negative cycle that is visible from s.
This is because the contrapositive is true: if there are no negative cycles visible from s, then
the l-values don’t change in round n. See previous slide.

How about the converse?

If the l-values of the nodes don’t change in round n, then there is no negative cycle visible
from s.
In this case ∀(u, v) ∈ E : l(u) + w(u, v) ≥ l(v)
So, for a cycle v0 − v1 − · · · − vt−1 − vt = v0
t
� t
� t
� t
�
l(vi ) ≤ (l(vi−1 ) + w(vi−1 , vi )) = l(vi−1 ) + w(vi−1 , vi )
i=1 i=1 i=1 i=1

Equal!

t
�
=⇒ 0 ≤ w(vi−1 , vi ) Cycle is not negative.
i=1
 Visible Negative Cycles

(1) Apply the MBF algorithm to the graph

(2) For all edges in E do
(a) if ( l(u) + w(u,v) < l(v) ) then
(i) Output TRUE Yes, there is a negative cycle

(3) Output FALSE No negative cycles

 Visible Negative Cycles

(1) Apply the MBF algorithm to the graph O(|E||V|)

(2) For all edges in E do O(|E|)

(a) if ( l(u) + w(u,v) < l(v) ) then

(i) Output TRUE
(3) Output FALSE

Running time is O(|E||V|)

 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 2 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 2 0 2 -1 -4 -3 -1
The MBF step is finished at
7 0 2 -3 2 -1 -4 -6 -1
this point. We run one more
8 0 4 -3 -1 -4 -4 -6 -4 step
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 2 0 2 -1 -4 -3 -1
7 0 2 -3 2 -1 -4 -6 -1
8 0 2 -3 -1 -4 -4 -6 -4

These values changed, so we have

at least one negative cycle.
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 2 0 2 -1 -4 -3 -1
7 0 2 -3 2 -1 -4 -6 -1
8 0 2 -3 -1 -4 -4 -6 -4

To find one, we follow the arrows

in the reverse direction towards s
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 2 0 2 -1 -4 -3 -1
7 0 2 -3 2 -1 -4 -6 -1
8 0 2 -3 -1 -4 -4 -6 -4

If the path crosses the same column twice, then the corresponding
node is on a negative cycle
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 2 0 2 -1 -4 -3 -1
7 0 2 -3 2 -1 -4 -6 -1
8 0 2 -3 -1 -4 -4 -6 -4

If the path crosses the same column twice, then the corresponding
node is on a negative cycle
 Karp’s Algorithm

What is the smallest average weight of a cycle in the graph?

2 5
C : v0 − v1 − · · · − vt−1 − vt = v0 3

4
t
� 2
1 s=1 4
-2
-3
µ(C) := w(vi−1 , vi ) 4
7
t i=1 3 4 -2
2 2
1
6 -2
8
3

Average weight of this cycle is (-2-3+1+2)/4 = -1/2

1
µ∗ (G) ≤ −
2

µ∗ (G) := min µ(C)

C cycle in G

Karp has designed an algorithm to compute this number which we will study in the following.
 Karp’s Algorithm: First Step

For k from 0 to n calculate the shortest path from s to all v using exactly k edges.
Set value to infinity if no such path exists.
This is the same as adding all non-existent edges to the graph with
a weight of infinity, and calculating shortest paths with exactly k
edges

Solution: dynamic programming.

�
0 if v = s
F0 (v) :=
∞ else

And for k=1,...,n

�
min(u,v)∈E Fk−1 (u) + w(u, v) if ∃(u, v) ∈ E
Fk (v) :=
∞ else

Extend to path to u by one more edge to obtain path with k edges

 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
1 0 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
2 0 4 inf 4 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
3 0 4 9 4 2 -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
4 0 4 0 4 2 -1 -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
5 0 4 0 2 -1 -1 -3 -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
6 0 4 0 2 -1 -4 -3 -1
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
7 0 4 -3 2 -1 -4 -6 -1
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
8 0 4 -3 -1 -4 -4 -6 -4
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4
 Reading the Paths
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

-3-1 Current path

 Reading the Paths
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

-6-3-1 Current path

 Reading the Paths
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

-5-6-3-1 Current path

 Reading the Paths
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

-7-5-6-3-1 Current path

 Reading the Paths
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

-6-7-5-6-3-1 Current path

 Reading the Paths
2 5
3

2x
-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

-5-6-7-5-6-3-1 Current path

 Reading the Paths
2 5
3

2x
-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

-4-5-6-7-5-6-3-1 Current path

 Reading the Paths
2 5
3

2x
-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4 Follow the arrows backwards

1-4-5-6-7-5-6-3-1 Current path

 Karp’s Algorithm: Second Step

Now we have calculated Fk(v) for all k=0,...,n and all nodes v.
For all v, calculate
Fn (v) − Fk (v)
α(v) := max
0≤k<n n−k
Karp’s theorem says:

µ∗ (G) = min α(v)

v∈V
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4

alpha(3) = max( (-2+3)/1, (-2-6)/2, (-2-inf)/3, (-2-0)/4, (-2-9)/5,(-2-inf)/8)=

max(1,-4,-inf,-1/2,-11/5) = 1
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4
alpha 0 5 1 -5/7 -1 5 1 -1
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4
alpha 0 5 1 -5/7 -1 5 1 -1

(-4-2)/(8-2)=-1
 Example
2 5
3

-2 2
s=1 4 -3
4
7
4 -2
3
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4
alpha 0 5 1 -5/7 -1 5 1 -1 µ∗ (G) = −1

(-4-2)/(8-2)=-1
 What does it Have to do with Cycles?
2 5
3

2x
2x
-2 2
s=1 4 -3
4
7
4 -2
3

2x
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4
alpha 0 5 1 -5/7 -1 5 1 -1

Path of length 8
and cost -4
 What does it Have to do with Cycles?
2 5
3

2x
2x
-2 2
s=1 4 -3
4
7
4 -2
3

2x
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8 Path of length 2
and cost 2
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
F4(v) 4 12 inf 0 11 8 inf -3 8
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4
alpha 0 5 1 -5/7 -1 5 1 -1
 What does it Have to do with Cycles?
2 5
3

2x
2x
-2 2
s=1 4 -3
4
7
4 -2
3

2x
2 2
1
6 -2
8
3

1 2 3 4 5 6 7 8
Fo(v) 0 0 inf inf inf inf inf inf inf
F1(v) 1 inf 4 inf 4 inf inf inf inf
F2(v) 2 inf inf inf inf 2 8 inf inf
F3(v) 3 inf 5 9 inf inf -1 6 inf
What remains is a cycle with
F4(v) 4 12 inf 0 11 8 inf -3 8 6 edges and cost -6
F5(v) 5 3 11 inf 2 -1 5 inf -1
F6(v) 6 inf 2 6 7 0 -4 3 inf
F7(v) 7 9 3 -3 8 5 -3 -6 5
F8(v) 8 0 8 -2 -1 -4 2 -5 -4
alpha 0 5 1 -5/7 -1 5 1 -1

Fn(v)-Fk(v) is the weight of a cycle with n-k edges starting and ending in v
 Proof of Karp’s Therem

Now we have calculated Fk(v) for all k=0,...,n and all nodes v.
For all v, calculate
Fn (v) − Fk (v)
α(v) := max
0≤k<n n−k
Karp’s theorem says:

µ∗ (G) = min α(v)

v∈V
 First Step: Zero Cycles

Consider the graph Ĝ obtained from G by subtracting from all edge values the quantity µ∗ (G)
µ∗ (Ĝ) = 0
Proof: weights in new graph are ŵ(u, v) = w(u, v) − µ∗ (G)

Average weight of a cycle in the new graph is

t
1�
ŵ(vi−1 , vi ) = µ(C) − µ∗ (G)
t i=1

All cycle weights in the old graph are at least µ∗ (G) .

So, smallest average weight cycle weight in new graph is 0. Q.E.D.

Without loss of generality: consider a graph in which smallest average cycle length is 0.
 Second Step:
Zero is Smallest Average Cycle Weight

Need to show that

Fn (v) − Fk (v)
min max =0
v∈V 0≤k<n n−k
Since µ∗ (G) = 0 , there are no negative cycles in the graph, so

σ := min Fk (v)
k=0,...,n−1

is the length of the shortest path from s to v. On the other hand, Fn(v) is the length of the
shortest path from s to v with exactly n edges, so it is not smaller than σ. Therefore

max Fn (v) − Fk (v) ≥ 0

k=0,...,n−1

We therefore see that

Fn (v) − Fk (v)
min max ≥0
v∈V 0≤k<n n−k

Need to show: there are v and k such that Fn (v) − Fk (v) = 0

 Second Step:
Zero is Smallest Average Cycle Weight
Need to show: there are v and k such that Fn (v) − Fk (v) = 0

Path P

Take cycle C of weight 0, node w on C, and simple path P Cycle of weight 0

w
from s to w. Simple path is one in which no node is repeated s Iterate n times

Extend path P by n iterations of cycle C to obtain a path P’.

This path has at least n edges.
Let Q be the path formed by the first n edges of P’ Path Q

v is final node on path Q

v w
Q : s = v0 → v1 → · · · → vn−1 → vn = v s
 Second Step:
Zero is Smallest Average Cycle Weight
Need to show: there are v and k such that Fn (v) − Fk (v) = 0

Path P

Take cycle C of weight 0, node w on C, and simple path P Cycle of weight 0

w
from s to w. Simple path is one in which no node is repeated s Iterate n times

Extend path P by n iterations of cycle C to obtain a path P’.

This path has at least n edges.
Let Q be the path formed by the first n edges of P’ Path Q

v is final node on path Q

v w
Q : s = v0 → v1 → · · · → vn−1 → vn = v s

k smallest index such that v = vk Note: k < n by choice of path

Then, Fk(v) = Fn(v) since cycle C has zero weight Q.E.D.

 Karp’s Algorithm

(1) Set F0(s)=0, F0(v)=inf for v not s Initiatlization

(2) For i from 1 to n do

This loop calculates
(i) For v in V set Fi(v) = inf the Fi(v) for all v in
V and all i from 0
(ii) For (u,v) in E do to n

(a) Set Fi(v) = min( Fi(v), Fi-1(v)+w(u,v))

(3) For v in V do
(i) Set alpha(v)=-inf
This loop calculates
the alpha values
(ii) For i from 1 to n-1 do
(a) Set alpha(v) = max( alpha(v), (Fn(v)-Fi(v))/(n-i))
(4) Set mu=alpha(s)
(5) For v in V do This loop calculates
the final result
(i) Set mu = min(mu, alpha(v))
(6) Return mu
 Karp’s Algorithm

(1) Set F0(s)=0, F0(v)=inf for v not s O(n)

(2) For i from 1 to n do

O(|E| n)
(i) For v in V set Fi(v) = inf
(ii) For (u,v) in E do
(a) Set Fi(v) = min( Fi(v), Fi-1(v)+w(u,v))
(3) For v in V do
(i) Set alpha(v)=-inf
O(n2)
(ii) For i from 1 to n-1 do
(a) Set alpha(v) = max( alpha(v), (Fn(v)-Fi(v))/(n-i))
(4) Set mu=alpha(s)
(5) For v in V do O(n)
(i) Set mu = min(mu, alpha(v))
(6) Return mu

Running time is O(|E||V|)