Introducting Example: Shortest Paths in Weighted Graphs

Shortest Path Problems

1. Single Pair Shortest Path

• Input: A directed edge-weighted graphs G = (V , E, w), a pair (s, t) of nodes from V
• Output:
• ∞, if t is not reachable from s,
• −∞, if there is a walk from s to t containing a negative cycle,
• a shortest path from s to t, otherwise
2. Single Source Shortest Path
• Input: A directed edge-weighted graph G = (V , E, w), a source s ∈ V .
• Output: The output of Single Pair Shortest Path for all pairs (s, v), v ∈ V
3. All Pairs Shortest Path
• Input: A directed edge-weighted graph G = (V , E, w)
• Output: The output of Single Pair Shortest Path for all pairs (u, v), u, v ∈ V

18
Walks, Paths, Cycles

• Inputs for Shortest Path Problems are directed weighted graphs G = (V , E, w) with
edge weight function w : E −→ IR .
• Weight of edge sets E ′ ⊆ E: w(E ′ ) = e∈E ′ w(e).
P

• Walks: A sequence of consecutive edges

p = ((v0 , v1 ), (v1 , v2 ), · · · , (vk−2 , vk−1 ), (vk−1 , vk ))

is called walk in G from v0 to vk of length k.

• Paths: The walk p is called path if vi ̸= vj for all 1 ≤ i < j ≤ k.
• Cycles: The path p is called cycle if v0 = vk .
• Shortest Paths: A path p from a node u to a node v is called shortest path from u
to v if for all paths p′ from u to v it holds w(p′ ) ≥ w(p).

19
Example G, w, s for the Single Source Shortest Path Problem

5 2
9
2 3

s 10 t 1 x 4

6 z

20
Output Shortest Path Tree with Root s

5
y

5 2
9
2 3

s 10 t 1 x 4
7
0 8 9
6 z

21
Distances in Weighted Graphs G = (V , E, w)

The Distance δG (u, v) from node u to node v is defined to be

• δG (u, v) = ∞ if v is not reachable from u in G (i.e., there is no walk from u to v).

• δG (u, v) = −∞ if there is a walk from u to v containing a cycle K of negative weight
(i.e., there are arbitrarily short walks from u to v obtained by going through K
correspondingly often).
• δG (u, v) = w(p) if v is reachable from u in G and no walk from u to v contains a
negative cycle and p denotes a shortest path from u to v.

22
Property 1 of Shortest Paths, the Number of Edges
Lemma 6
Let G = (V , E, w) be a weighted graph, and let s, u, v ∈ V .
If −∞ < δG (u, v) < ∞ then there is a shortest walk p from u to v which is a path and
which has at most |V | − 1 edges.

Proof of 1: Assume that p′ is a shortest walk from u to v which contains cycles.

Then each cycle has non negative weight and can be removed.

Note: Each path (without cycles) in G has at most |V | − 1 edges. □

s 2 v1 −1 v2 3 v3 1 v

−2 1

w1 1 w2
23
Property 1 of Shortest Paths, the Number of Edges

Lemma 7
Let G = (V , E, w) be a weighted graph, and let s, u, v ∈ V .
If −∞ < δG (u, v) < ∞ then there is a shortest walk p from u to v which is a path and
which has at most |V | − 1 edges.

Proof of 1: Assume that p′ is a shortest walk from u to v which contains cycles.

Then each cycle has non negative weight and can be removed.

Note: Each path (without cycles) in G has at most |V | − 1 edges. □

s 2 v1 −1 v2 3 v3 1 v

24
Property 2 of Shortest Paths, Monotonicity
Lemma 8
Let G = (V , E, w) be a weighted graph, and let s, u, v ∈ V .

Let p be a shortest path from u to v passing two nodes w and z in this order.

Then the subpath of p from w to z is also a shortest path.

Proof:

If there were a shorter path from w to z we could construct a shorter path from u to v.

s 2 v1 −1 v2 3 v3 1 v4 −1 v5

2 2

w1

25
Property 3 of Shortest Paths, Triangle Inequality
Lemma 9

Let G = (V , E, w) be a weighted graph, let s ∈ V and (u, v) ∈ E. Then

δG (s, v) ≤ δG (s, u) + w(u, v).

Proof: There are three cases:

1. u is not reachable from s, i.e., u.d = ∞.

Then δG (s, v) ≤ ∞ + w(u, v) = ∞.
2. u is reachable from s, but there is no shortest path from s to v going through u.
Then δG (s, v) < δG (s, u) + w(u, v).
3. u is reachable from s and there is a shortest path from s to v going through u.
Then δG (s, v) = δG (s, u) + w(u, v).

26
Basic Operations Initialize and Relax

Initialize(G, s) Relax(u, v, w)
1 For all v ∈ V 1 If v.d > u.d + w(u, v)
2 do v.d ← ∞ 2 // Relax edge (u, v)
3 v.π ← NIL 3 then v.d ← u.d + w(u, v)
4 s.d ← 0 4 v.π ← u
Running time O(|V |). Running time O(1).

27
The Effect of Relax, 1

Relax(u, v, w)

1 If v.d > u.d + w(u, v)

2 then v.d ← u.d + w(u, v)
3 v.π ← u

If u.d < ∞ und v.d = ∞ then Relax(u, v, w) discovers a path from s to v.

0 2 ∞

s 2 u −1 v

28
The Effect of Relax, 1

Relax(u, v, w)

1 If v.d > u.d + w(u, v)

2 then v.d ← u.d + w(u, v)
3 v.π ← u

If u.d < ∞ und v.d = ∞ then Relax(u, v, w) discovers a path from s to v.

0 2 1

s 2 u −1 v

29
The Effect of Relax, 2

Relax(u, v, w)
1 If v.d > u.d + w(u, v)
2 then v.d ← u.d + w(u, v)
3 v.π ← u

If ∞ > v.d > u.d + w(u, v) then Relax(u, v, w) discovers a shorter path from s to v
(namely this over u).

0 2 3 6 7

s 2 v1 1 v2 3 v3 1 v

1 1

v4 2 u

3 5 30
The Effect of Relax, 2

Relax(u, v, w)
1 If v.d > u.d + w(u, v)
2 then v.d ← u.d + w(u, v)
3 v.π ← u

If ∞ > v.d > u.d + w(u, v) then Relax(u, v, w) discovers a shorter path from s to v
(namely this over u).

0 2 3 6 6

s 2 v1 1 v2 3 v3 1 v

1 1

v4 2 u

3 5 31
Main Observation

Apply Initialize(G, s) and a finite sequence of RELAX-operations to G = (V , E, w).

Then one gets a subgraph Gπ = (Vπ , Eπ ), where

• Vπ = {v ∈ V , v.d < ∞}
• Eπ = {(v.π, v), v.π ̸= NIL}

How is Gπ looking like?

Lemma 10

Suppose that no negative cycle is reachable from s.

Then Gπ is always a tree with root s, and

For each v ∈ Vπ it holds that v.d = δGπ (s, v) ≥ δG (s, v).

I.e., v.d denotes the length of the path from s to v in the tree Gπ .
32
The Proof of Lemma 10, I

We assume Eπ ̸= ∅. Otherwise Vπ = {s}, which makes the Lemma trivially true.

Remember that a directed graph is a tree with root s if and only if for each node v there
is exactly one path from s to v.

We know that node s has indegree 0 and that all other nodes in Gπ have indegree 1.

This implies that Gπ is a disjoint union of one tree with root s and some cycles.

Consequently, we have to show that Gπ is acyclic.

We show that any cycle K = (v1 , · · · , vk , v1 ) in Gπ which is reachable from s in G has

negative weight.

33
Proof of Lemma 10, II

W.l.o.g. let (vk , v1 ) be the last edge in K , which is relaxed.

Consider the situation directly before relaxing (vk , v1 ).

• The edges (v1 , v2 ), · · · , (vk−1 , vk ) are already relaxed.

This implies
k
X
vk .d = vk−1 .d + w(vk−1 , vk ) = · · · = v1 .d + w(vi−1 , vi ).
i=2

• However, as (vk , v1 ) is going to be relaxed, v1 .d > vk .d + w(vk , v1 ).

This implies
k
X
v1 .d > v1 .d + w(vi−1 , vi ) + w(vk , v1 ) = v1 .d + w(K ).
i=2

Consequently w(K ) < 0. □ 34

Example Gπ with negative Cycle

∞ t

1 −3

∞ v 1 u ∞

35
Relax(s, t)

1 t

1 −3

∞ v 1 u ∞

36
Relax(s, t), Relax(t, u)

1 t

1 −3

∞ v 1 u −2

37
Relax(s, t), Relax(t, u), Relax(u, v)

1 t

1 −3

−1 v 1 u −2

38
Relax(s, t), Relax(t, u), Relax(u, v), Relax(v, t)

0 t

1 −3

−1 v 1 u −2

39
The Bellman-Ford Algorithm

BellmanFord(G, w, s)

1 Initialize(G, s)
2 For i ← 1 to |V | − 1
3 do for all (u, v) ∈ E
4 do Relax(u, v, w)
5 For all (u, v) ∈ E
6 do if v.d > u.d + w(u, v)
7 then return false , STOP
8 return true

Running time O(|V ||E|)

40
Example BellmanFord(G, s)

7
y ∞
8

−3
0 ∞
5
∞
s 6 t x 9
−2
7

−4 ∞
z

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 41
Round 1 (s, t)

7
y ∞
8

−3
0 6 5
∞
s 6 t x 9
−2
7

−4 ∞
z

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 42
Round 1 (s, t), (s, y)

7
y 7
8

−3
0 6 5
∞
s 6 t x 9
−2
7

−4 ∞
z

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 43
Runde 1 (s, t), (s, y), (t, x)

7
y 7
8

−3
0 6 5 11
s 6 t x 9
−2
7

−4 ∞
z

Kanten (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 44
Round 1 (s, t), (s, y), (t, x), (t, y)

7
y 7
8

−3
0 6 5 11
s 6 t x 9
−2
7

−4 ∞
z

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 45
Round 1 (s, t), (s, y), (t, x), (t, y), (t, z)

7
y 7
8

−3
0 6 5 11
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 46
Round 1 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t)

7
y 7
8

−3
0 6 5 11
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 47
Round 1 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 48
Round 1 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 49
Round 1 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 50
Round 1 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 51
Round 2 (s, t)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 52
Round 2 (s, t), (s, y)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 53
Round 2 (s, t), (s, y), (t, x)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 54
Round 2 (s, t), (s, y), (t, x), (t, y)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 55
Round 2 (s, t), (s, y), (t, x), (t, y), (t, z)

7
y 7
8

−3
0 6 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 56
Round 2 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 57
Round 2 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 58
Round 2 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 59
Round 2 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 60
Round 2 (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 61
Round 3 (s, t)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 62
Round 3 (s, t), (s, y)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 63
Round 3 (s, t), (s, y), (t, x)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 64
Round 3 (s, t), (s, y), (t, x), (t, y)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z 2

Edges (s, t), (s, y), (t, x)(t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 65
Round 3 (s, t), (s, y), (t, x), (t, y), (t, z)

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z −2

Edges (s, t), (s, y), (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, s), (z, x) 66
Output true

7
y 7
8

−3
0 2 5 4
s 6 t x 9
−2
7

−4
z −2

The remaining 5 Relax in Round 3 and those in Round 4 do not cause any change. 67
Correctness of the Bellman-Ford Algorithm, I

Theorem 11
BellmanFord(G, w, s) outputs true if and only if no negative cycle is reachable from s.

In this case, the output Gπ is a shortest path tree with root s which contains all nodes v
which are reachable from s.

Proof: Assume first that no negative cycle is reachable from s.

Let v ∈ V be reachable from s and P = (e1 , · · · , ek ) be a shortest path from s to v,

k ≤ |V | − 1.

For all i, 1 ≤ i ≤ k, let ei = (vi−1 , vi ) and v0 = s and vk = v.

We show by induction over i that for all i, 1 ≤ i ≤ k, it holds (vi ).d = δG (s, vi ) after round i.

Consequently, v.d = δG (s, v) after round k.

68
Correctness of the Bellman-Ford Algorithm, II

Case i = 1: In round 1, the edge e1 = (v0 , v1 ) is relaxed.

As (v0 ).d = 0, (v1 ).d gets value w(e1 ) which equals δG (s, v1 ), as p is a shortest path.

Case i > 1: In round i, edge ei = (vi−1 , vi ) is relaxed.

It holds (vi−1 ).d = δG (s, vi−1 ) (induction hypothesis).

Thus, (vi ).d gets value δG (s, vi−1 ) + w(ei ).

This equals δG (s, vi ), as p is a shortest path.

Thus, Gπ is a shortest path tree in G with root s.

Consequently, v.d = δG (s, v) for all v ∈ V .

This implies by Lemma 9 that v.d ≤ u.d + w(u, v) for all edges (u, v) ∈ E (Triangel
Inequality).
69
Correctness of the Bellman-Ford Algorithm, III

We still have to show that the Bellman-Ford Algorithm returns false if and only if G
contains a negative cycle reachable from s.

We showed already that if G does not contain a negative cycle reachable from s then the
output is true.

It remains to show that output true implies that G does not contain a negative cycle
reachable from s.

This follows from the following lemma.

Lemma 12
Suppose there is a function f : V −→ IR ∪ {∞} fulfilling f (v) ≤ f (u) + w(u, v) for all
edges (u, v) ∈ E, where f (v) ̸= ∞ for all nodes v reachable from s.

Then all cycles K = (v1 , · · · , vk , v1 ) which are reachable from s have non negative
weight.
70
Correctness of the Bellman-Ford Algorithm, IV

Proof of Lemma 12:

By assumption, for each cycle K = (v1 , · · · , vk , v1 ) reachable from s it holds

f (vi ) ≤ f (vi−1 ) + w(vi−1 , vi )

for all i = 2, · · · , k, and

f (v1 ) ≤ f (vk ) + w(vk , v1 ).

Summing up these k inequalities yields

k
X k−1
X k−1
X
f (vi ) + f (v1 ) ≤ f (vi ) + f (vk ) + w(vi−1 , vi ) + w(vk , v1 ).
i=2 i=1 i=2

Pk Pk
Consequently, i=1 f (vi ) ≤ i=1 f (vi ) + w(K ), which implies w(K ) ≥ 0. □
71