‫طراحی ا لگور یتم ها‬

‫مبحث سیزدهم‪:‬‬
‫کوتاه ترین مسیر در گراف‬
‫ﺳﺠﺎد ﺷﯿﺮﻋیل ﴲﺮﺿﺎ‬
‫ﲠﺎر ‪1401‬‬
‫ﯾﮏ ﺷﻨﺒﻪ‪ 20 ،‬ﻓﺮوردﯾﻦ ‪1402‬‬ ‫‪1‬‬
‫‪Based on Stanford CS161 Slides from Summer 2020 by Karey Shi‬‬
 ‫اﻃﻼع رﺳﺎ ﮲ﻰ‬
‫اب رای این س ‪15.3 :‬‬ ‫●‬
‫س‬ ‫دوم‪ :‬روز ی ش ب ه آ ه‪ 27 ،‬فروردین ‪ ،1402‬در سا‬ ‫● ام ا‬

‫‪2‬‬
‫یافتن کوتاه ترین مسیر در گراف‬

‫ﺗﻌﺮﯾﻒ ﻣﺴﺌﻠﻪ‬

‫‪3‬‬
SHORTEST PATHS IN WEIGHTED GRAPHS
Caltrain
Suppose you only know
your way around campus
via certain landmarks
Stadium

Gates

Memchu
Chipotle
Wilbur
Dining
Old Union

The Dish
4
SHORTEST PATHS IN WEIGHTED GRAPHS
We can represent this as a weighted graph Caltrain
where w(u,v) = weight of an edge (u, v). 4
12
For today, these weights are non-negative. Stadium
3
15
Gates
Note: All graphs are 2
directed, but to save the
trouble of drawing double
Memchu 2
arrows everywhere:
21 Chipotle
Wilbur
Old Union 1 Dining 10
=

15
The Dish
5
SHORTEST PATHS IN WEIGHTED GRAPHS
We can represent this as a weighted graph Caltrain
where w(u,v) = weight of an edge (u, v). 4
12
For today, these weights are non-negative. Stadium
3
15
Gates
What if we wanted to
2
compute the shortest path
from Gates to Old Union?
Memchu 2
21 Chipotle
Wilbur
Old Union 1 Dining 10

15
The Dish
6
SHORTEST PATHS IN WEIGHTED GRAPHS
The shortest path between v and w in Caltrain
a weighted graph is the path with the 4
minimum cost. 12
Stadium
Cost of a path 3
= 15
sum of weights along that path Gates
2
Memchu 2
21 Chipotle
Wilbur
Old Union 1 Dining 10

15
The Dish
7
SHORTEST PATHS IN WEIGHTED GRAPHS
The shortest path between v and w in Caltrain
a weighted graph is the path with the 4
minimum cost. 12
Stadium
Cost of a path 3
= 15
sum of weights along that path Gates
2
Memchu 2
21 Chipotle
Wilbur
Old Union 1 Dining 10
This path from Gates to
Old Union has cost 36. 15
The Dish
8
SHORTEST PATHS IN WEIGHTED GRAPHS
The shortest path between v and w in Caltrain
a weighted graph is the path with the 4
minimum cost. 12
Stadium
Cost of a path 3
= 15
sum of weights along that path Gates
2
Memchu 2
21 Chipotle
Wilbur
Old Union 1 Dining 10

15 This path from Gates to

The Dish
Old Union only has cost 5.
9
SHORTEST PATHS IN WEIGHTED GRAPHS
Caltrain
The distance d(v,w)
4
between 2 vertices v and w
is the cost of the shortest 12
Stadium
path between v and w 3
15
Gates
d(Gates, Old Union) = 5
2
Memchu 2
21 Chipotle
Wilbur
Old Union 1 Dining 10

15
The Dish
10
SINGLE-SOURCE SHORTEST PATH

Applications:
Finding the shortest/most efficient path from point A to point B via bike, walking, Uber, Lyft, train, etc.
(Edge weights could be time, money, hassle, effort)
Finding the shortest path to send packets from my computer to some desired server using the Internet
(Edge weights could be link length, traffic, cost, delay, etc.)

11
NEGATIVE CYCLES
If negative cycles exist in the graph, we’ll say no solution exists. Why?

-1 C -4

A B D E
2 3 5

What’s the shortest path from A to E?

Is it: A → B → C → D → E? Cost = 2 - 1 - 4 + 5 = 2.

12
NEGATIVE CYCLES
If negative cycles exist in the graph, we’ll say no solution exists. Why?

-1 C -4

A B D E
2 3 5

What’s the shortest path from A to E?

Is it: A → B → C → D → E? Cost = 2 - 1 - 4 + 5 = 2.
Or is it: A → B → C → D → B → C → D → B → C → D → B → C → D → B → C → D → E ?

Basically, shortest paths aren’t defined if there are negative cycles! 13

‫ﺳﻮال؟‬
‫‪14‬‬
 ‫ا لگور یتم بلمن‪-‬فورد‬

‫ﭘﯿﺪا ﮐﺮدن ﮐﻮاته ﺗﺮﯾﻦ ﻣﺴﯿﺮ از ﯾﮏ راس ﺑﻪ ﲤﺎم رﺋﻮس‬

‫‪15‬‬
BELLMAN-FORD
We maintain a list d(k) of length n, for each k = 0, 1, …, n–1.
d(k)[b] = the cost of the shortest path from s to b with at most k edges.
s x y z
(0)
0 2 ∞
d 0 ∞ ∞ ∞ s x
1
We know how to fill in
d(1)
d(0) -- the costs of 2
shortest paths to 5
each vertex with at
most k = 0 edges in it d(2)
z y
-2
d(3)
∞ ∞
16
BELLMAN-FORD
We maintain a list d(k) of length n, for each k = 0, 1, …, n–1.
d(k)[b] = the cost of the shortest path from s to b with at most k edges.
s x y z
(0)
0 2 ∞
d 0 ∞ ∞ ∞ s x
1
We will use table
d(1)
d(0) to fill in d(1). 2
More generally, 5
we will use table
d(k-1) to fill in d(k). d(2)
z y
-2
d(3)
∞ ∞
17
BELLMAN-FORD
We maintain a list d(k) of length n, for each k = 0, 1, …, n–1.
d(k)[b] = the cost of the shortest path from s to b with at most k edges.

How do we use d(0) to update d(1)[b]?

18
BELLMAN-FORD
We maintain a list d(k) of length n, for each k = 0, 1, …, n–1.
d(k)[b] = the cost of the shortest path from s to b with at most k edges.

How do we use d(0) to update d(1)[b]?

Case 1: the shortest path from s to b with at most k edges could be one with at most k–1 edges! In
other words, allowing k edges is not going to change anything. Then:
d(k)[b] = d(k-1)[b]

19
BELLMAN-FORD
We maintain a list d(k) of length n, for each k = 0, 1, …, n–1.
d(k)[b] = the cost of the shortest path from s to b with at most k edges.

How do we use d(0) to update d(1)[b]?

Case 1: the shortest path from s to b with at most k edges could be one with at most k–1 edges! In
other words, allowing k edges is not going to change anything. Then:
d(k)[b] = d(k-1)[b]
Case 2: the shortest path from s to b with at most k edges could be one with exactly k edges!

20
BELLMAN-FORD
We maintain a list d(k) of length n, for each k = 0, 1, …, n–1.
d(k)[b] = the cost of the shortest path from s to b with at most k edges.

How do we use d(0) to update d(1)[b]?

Case 1: the shortest path from s to b with at most k edges could be one with at most k–1 edges! In
other words, allowing k edges is not going to change anything. Then:
d(k)[b] = d(k-1)[b]
Case 2: the shortest path from s to b with at most k edges could be one with exactly k edges!
I.e. this length-k shortest path is [length k–1 shortest path to some incoming neighbor a] + w(a,b).
Which of b’s incoming neighbors will offer this shortest path? Let’s check them all:
d(k)[b] = mina in b’s incoming neighbors{ d(k-1)[a] + w(a,b) }

21
BELLMAN-FORD PSEUDOCODE
BELLMAN_FORD(G,s):
d(k) = [] for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0
for k = 1, ..., n–1:
for b in V:
d(k)[b] ← min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }
return d(n-1)

22
BELLMAN-FORD PSEUDOCODE
Keeping all n–1 rows is a simplification to
BELLMAN_FORD(G,s): make the pseudocode straightforward. In
(k) practice, we’d only keep 2 of them at a time!
d = [] for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0
for k = 1, ..., n–1:
for b in V:
d(k)[b] ← min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }
return d(n-1)

23
 BELLMAN-FORD PSEUDOCODE
Keeping all n–1 rows is a simplification to
BELLMAN_FORD(G,s): make the pseudocode straightforward. In
(k) practice, we’d only keep 2 of them at a time!
d = [] for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0
Fill the first row
for k = 1, ..., n–1:
for b in V:
d(k)[b] ← min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }
return d(n-1)

24
 BELLMAN-FORD PSEUDOCODE
Keeping all n–1 rows is a simplification to
BELLMAN_FORD(G,s): make the pseudocode straightforward. In
(k) practice, we’d only keep 2 of them at a time!
d = [] for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0 Take the minimum over all incoming
for k = 1, ..., n–1: neighbors a (i.e. all a s.t. (a, b) ∈ E)
Fill the first row This takes O(deg(b))!!!
for b in V:
d(k)[b] ← min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }
return d(n-1) CASE 1 CASE 2

25
 BELLMAN-FORD PSEUDOCODE
Keeping all n–1 rows is a simplification to
BELLMAN_FORD(G,s): make the pseudocode straightforward. In
(k) practice, we’d only keep 2 of them at a time!
d = [] for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0 Take the minimum over all incoming
for k = 1, ..., n–1: neighbors a (i.e. all a s.t. (a, b) ∈ E)
Fill the first row This takes O(deg(b))!!!
for b in V:
d(k)[b] ← min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }
return d(n-1) CASE 1 CASE 2

The answer

26
 BELLMAN-FORD PSEUDOCODE
Keeping all n–1 rows is a simplification to
BELLMAN_FORD(G,s): make the pseudocode straightforward. In
(k) practice, we’d only keep 2 of them at a time!
d = [] for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0 Take the minimum over all incoming
for k = 1, ..., n–1: neighbors a (i.e. all a s.t. (a, b) ∈ E)
Fill the first row This takes O(deg(b))!!!
for b in V:
d(k)[b] ← min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }
return d(n-1) CASE 1 CASE 2

The answer
Runtime: ?
27
 BELLMAN-FORD PSEUDOCODE
Keeping all n–1 rows is a simplification to
BELLMAN_FORD(G,s): make the pseudocode straightforward. In
(k) practice, we’d only keep 2 of them at a time!
d = [] for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0 Take the minimum over all incoming
for k = 1, ..., n–1: neighbors a (i.e. all a s.t. (a, b) ∈ E)
Fill the first row This takes O(deg(b))!!!
for b in V:
d(k)[b] ← min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }
return d(n-1) CASE 1 CASE 2

The answer
Runtime: O(m·n)
28
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 ∞
d 0 ∞ ∞ ∞ s x
1
We will use table
d(1)
d(0) to fill in d(1). 2
More generally, 5
we will use table
d(k-1) to fill in d(k). d(2)
z y
-2
d(3)
∞ ∞
29
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 ∞
d 0 ∞ ∞ ∞ s x
1
This is min of:
d(1) 0
2
5
(0)
d [s]
(0)
d [x] + w(x, s)
d(2)
z y
-2
d (3)
∞ ∞
30
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 ∞
d 0 ∞ ∞ ∞ s x
1
This is min of:
d(1) 0 2
2
5
(0)
d [x]
(0)
d [s] + w(s, x)
d(2)
z y
-2
d (3)
∞ ∞
31
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 ∞
d 0 ∞ ∞ ∞ s x
1
This is min of:
d(1) 0 2 5
2
5
(0)
d [y]
(0)
d [s] + w(s, y)
d(2)
d(0)[x] + w(x, y)
z y
-2
d (3)
∞ ∞
32
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 ∞
d 0 ∞ ∞ ∞ s x
1
This is min of:
d(1) 0 2 5 ∞
2
5
(0)
d [z]
(0)
d [y] + w(y, z)
d(2)
z y
-2
d (3)
∞ ∞
33
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
Now, fill in d(1) 0 2 5 ∞
2
d(2)!!! 5
d(2)
z y
-2
d (3)
∞ 5
34
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(1)[s]
d(1)[x] + w(x, s) d(2) 0
z y
-2
d (3)
∞ 5
35
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(1)[x]
d(1)[s] + w(s, x) d(2) 0 2
z y
-2
d (3)
∞ 5
36
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(1)[y]
d(1)[s] + w(s, y) d(2) 0 2 4
d(1)[x] + w(x, y) z y
-2
d (3)
∞ 5
37
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(1)[z]
d(1)[y] + w(y, z) d(2) 0 2 4 3
z y
-2
d (3)
3 5
38
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
Now, fill in d(1) 0 2 5 ∞
2
d(3)!!! 5
d(2) 0 2 4 3
z y
-2
d (3)
3 4
39
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(2)[s]
d(2)[x] + w(x, s) d(2) 0 2 4 3
z y
-2
d (3)
0 3 4
40
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(2)[x]
d(2)[s] + w(s, x) d(2) 0 2 4 3
z y
-2
d (3)
0 2 3 4
41
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(2)[y]
d(2)[s] + w(s, y) d(2) 0 2 4 3
d(2)[x] + w(x, y) z y
-2
d (3)
0 2 4 ∞
3 5
4
42
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
d(1) 0 2 5 ∞
This is min of: 2
5
d(2)[z]
d(2)[y] + w(y, z) d(2) 0 2 4 3
z y
-2
d (3)
0 2 4 2 3 4
43
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
s x y z
(0)
0 2 2
d 0 ∞ ∞ ∞ s x
1
Weʼre done! d(1) 0 2 5 ∞
2
We can double check the
entry for z in each d(i):
5
d(2) 0 2 4 3
z y
-2
d(3)
0 2 4 2 2 4
44
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
Just to double s x y z
check: 0 2 2
d(0) 0 ∞ ∞ ∞ s x
1
cost of shortest path from
d(1) 0 2 5 ∞
s to z with 1 edge = ∞
2
5
d(2) 0 2 4 3
z y
-2
d(3)
0 2 4 2 2 4
45
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
Just to double s x y z
check: 0 2 2
d(0) 0 ∞ ∞ ∞ s x
1
cost of shortest path from
d(1) 0 2 5 ∞
s to z with 1 edge = ∞
2
5
cost of shortest path from
s to z with 2 edges = 3 d(2) 0 2 4 3
z y
-2
d(3)
0 2 4 2 2 4
46
 BELLMAN-FORD
We store a list d(k) of length n, for each k = 0, 1, …, n–1. for k = 1, ..., n–1:
for b in V:
d(k)[b] = cost of shortest path from s to b w/ at most k edges.
d(k)[b] ← min{d(k-1)[b], mina{d(k-1)[a] +
w(a,b)}}
Just to double s x y z
check: 0 2 2
d(0) 0 ∞ ∞ ∞ s x
1
cost of shortest path from
d(1) 0 2 5 ∞
s to z with 1 edge = ∞
2
5
cost of shortest path from
s to z with 2 edges = 3 d(2) 0 2 4 3
z y
-2
2 4
cost of shortest path from (3)
s to z with 3 edges = 2 d 0 2 4 2

47
‫ﺳﻮال؟‬
‫‪48‬‬
 ‫پیاده سازی دیگری از‬
‫ا لگور یتم بلمن‪-‬فورد‬
‫ﭘﯿﺪا ﮐﺮدن ﮐﻮاته ﺗﺮﯾﻦ ﻣﺴﯿﺮ از ﯾﮏ راس ﺑﻪ ﲤﺎم رﺋﻮس‬

‫‪49‬‬
DYNAMIC PROGRAMMING
Two approaches for DP
(2 different ways to think about and/or implement DP algorithms)

Bottom-up: iterates through problems by size and solves the small

problems first (kind of like taking care of base cases first & building up).
e.g. Bellman-Ford (as we just saw) computes d(0), then d(1), then d(2), etc.

Top-down: instead uses recursive calls to solve smaller problems, while

using memoization/caching to keep track of small problems that you’ve
already computed answers for (simply fetch the answer instead of
re-solving that problem and waste computational effort)
We will see another way to implement Bellman-Ford using a top-down approach.

50
TOP-DOWN BELLMAN-FORD
RECURSIVE_BELLMAN_FORD(G,s):
d(k) = [None] * n for k = 0, ..., n–1
d(0)[v] = ∞ for all v in V (except s)
d(0)[s] = 0
for b in V:
d(n-1)[b] ← RECURSIVE_BF_HELPER(G, b, n–1)

RECURSIVE_BF_HELPER(G, b, k):
A = {a such that (a,b) in E} ∪ {b} // b’s in-neighbors
for a in A:
if d(k-1)[a] is None: // not yet solved
d(k-1)[a] ← RECURSIVE_BF_HELPER(G, a, k-1)
return min{ d(k-1)[b], mina{d(k-1)[a] + w(a,b)} }

51
TOP-DOWN BELLMAN-FORD
RECURSIVE_BELLMAN_FORD(G,s): Think of this as a
d(k) = [None] * n for k = 0, ..., n–1 table/cache that holds the
d(0)[v] = ∞ for all v in V (except s) computed answers of our
subproblems.
d(0)[s] = 0
for b in V:
d(n-1)[b] ← RECURSIVE_BF_HELPER(G, b, n–1)

RECURSIVE_BF_HELPER(G, b, k): if the answer to this

A = {a such that (a,b) in E} ∪ {b} // b’s in-neighbors subproblem hasnʼt
for a in A: been computed yet,
if d(k-1)[a] is None: // not yet solved then weʼll first solve
it! It immediately
d(k-1)[a] ← RECURSIVE_BF_HELPER(G, a, k-1) gets saved in our
(k-1) (k-1)
return min{ d [b], mina{d [a] + w(a,b)} } cache, so we wonʼt
ever solve it twice.

52
TOP-DOWN BELLMAN-FORD
RECURSIVE_BELLMAN_FORD(G,s): Think of this as a
d(k) = [None] * n for k = 0, ..., n–1 table/cache that holds the
d(0)[v] = ∞ for all v in V (except s) computed answers of our
subproblems.
d(0)[s] = 0
for b in V:
d(n-1)[b] ← RECURSIVE_BF_HELPER(G, b, n–1)

RECURSIVE_BF_HELPER(G, b, k): if the answer to this

A = {a such that (a,b) in E} ∪ {b} // b’s in-neighbors subproblem hasnʼt
for a in A: been computed yet,
if d(k-1)[a] is None: // not yet solved then weʼll first solve
it! It immediately
d(k-1)[a] ← RECURSIVE_BF_HELPER(G, a, k-1) gets saved in our
(k-1) (k-1)
return min{ d [b], mina{d [a] + w(a,b)} } cache, so we wonʼt
ever solve it twice.
Runtime: ? 53
TOP-DOWN BELLMAN-FORD
RECURSIVE_BELLMAN_FORD(G,s): Think of this as a
d(k) = [None] * n for k = 0, ..., n–1 table/cache that holds the
d(0)[v] = ∞ for all v in V (except s) computed answers of our
subproblems.
d(0)[s] = 0
for b in V:
d(n-1)[b] ← RECURSIVE_BF_HELPER(G, b, n–1)

RECURSIVE_BF_HELPER(G, b, k): if the answer to this

A = {a such that (a,b) in E} ∪ {b} // b’s in-neighbors subproblem hasnʼt
for a in A: been computed yet,
if d(k-1)[a] is None: // not yet solved then weʼll first solve
it! It immediately
d(k-1)[a] ← RECURSIVE_BF_HELPER(G, a, k-1) gets saved in our
(k-1) (k-1)
return min{ d [b], mina{d [a] + w(a,b)} } cache, so we wonʼt
ever solve it twice.
Runtime: O(m·n) 54
‫ا لگور یتم فلوید‪-‬وارشال‬

‫ﭘﯿﺪا ﮐﺮدن ﮐﻮاته ﺗﺮﯾﻦ ﻣﺴﯿﺮ ﺑﯿﻦ ﻫﺮ دو راس‬

‫‪55‬‬
ALL-PAIRS SHORTEST PATHS (APSP)
Find the shortest paths from v to w for ALL pairs v, w of vertices in the graph
(not just shortest paths from a special single source s)

Destination 2
a b c d a b
1
a 0 2 4 2

b 1 0 2 0 2
Source

5
c ∞ ∞ 0 -2

d ∞ ∞ ∞ 0 d c
-2

56
ALL-PAIRS SHORTEST PATHS (APSP)
Find the shortest paths from v to w for ALL pairs v, w of vertices in the graph
(not just shortest paths from a special single source s)

Destination 2
a b c d a b
1
a 0 2 4 2

b 1 0 2 0 2
Source

5
c ∞ ∞ 0 -2

d ∞ ∞ ∞ 0 d c
-2
What’s a naive algorithm? 57
ALL-PAIRS SHORTEST PATHS (APSP)
Find the shortest paths from v to w for ALL pairs v, w of vertices in the graph
(not just shortest paths from a special single source s)
Naive algorithm (if we want to handle negative edge weights):
Destination 2
a b c d a b
For all s in G:
1
a 0 Run2 Bellman-Ford
4 2 on G starting at s

b 1 0 2 0 2
Source

5
c ∞ ∞ 0 -2

d ∞ ∞ ∞ 0 d c
-2
What’s a naive algorithm? 58
ALL-PAIRS SHORTEST PATHS (APSP)
Find the shortest paths from v to w for ALL pairs v, w of vertices in the graph
(not just shortest paths from a special single source s)
Naive algorithm (if we want to handle negative edge weights):
Destination 2
a b c d a b
For all s in G:
1
a 0 Run2 Bellman-Ford
4 2 on G starting at s

b 1 0 2 0 Runtime: ? 2
Source

5
c ∞ ∞ 0 -2

d ∞ ∞ ∞ 0 d c
-2
What’s a naive algorithm? 59
ALL-PAIRS SHORTEST PATHS (APSP)
Find the shortest paths from v to w for ALL pairs v, w of vertices in the graph
(not just shortest paths from a special single source s)
Naive algorithm (if we want to handle negative edge weights):
Destination 2
a b c d a b
For all s in G:
1
a 0 Run2 Bellman-Ford
4 2 on G starting at s

b 1O(n ·mn)
0 0 2)... this may be as5bad as n4 if m2 = n2
2= O(mn
Source

Runtime:
c ∞ ∞ 0 -2
Can we do better?
d c
d ∞ ∞ ∞ 0 -2
What’s a naive algorithm? 60
FLOYD-WARSHALL: A DP APPROACH
We need to define the optimal substructure: Figure out what your subproblems are, and
how you’ll express an optimal solution in terms of optimal solutions to subproblems.

61
FLOYD-WARSHALL: A DP APPROACH
We need to define the optimal substructure: Figure out what your subproblems are, and
how you’ll express an optimal solution in terms of optimal solutions to subproblems.

Subproblem(k): for all pairs v, w, find the cost of the shortest path from v
to w so that all the internal vertices on that path are in {1, …, k}
Let D(k)[v, w] be the solution to Subproblem(k)
Assign each vertex a
number in {1, 2..., n} k+1 n
1
w
v 3 ···

(This diagram omits 2 k

many edges and nodes,
so itʼs not a full example) ··· Vertices 1, … k k+2 62
FLOYD-WARSHALL: A DP APPROACH
We need to define the optimal substructure: Figure out what your subproblems are, and
how you’ll express an optimal solution in terms of optimal solutions to subproblems.

Subproblem(k): for all pairs v, w, find the cost of the shortest path from v
to w so that all the internal vertices on that path are in {1, …, k}
Let D(k)[v, w] be the solution to Subproblem(k)
Assign each vertex a
number in {1, 2..., n} k+1 n
1
w
v 3 ···
This is the shortest path
(This diagram omits 2 k from v to w through the
green set. It has cost
many edges and nodes,
so itʼs not a full example) ··· Vertices 1, … k k+2 D(k)[v, w]
63
FLOYD-WARSHALL: A DP APPROACH
We need to define the optimal substructure: Figure out what your subproblems are, and
how you’ll express an optimal solution in terms of optimal solutions to subproblems.

Subproblem(k): for all pairs v, w, find the cost of the shortest path from v
to w so that all the internal vertices on that path are in {1, …, k}
Let D(k)[v, w] be the solution to Subproblem(k)
Assign each vertex a
number in {1, 2..., n} k+1 n
1
w
v (k)
1 ···
How do I compute D [v, w] using answers to smaller subproblems?
This is the shortest path
(This diagram omits 2 k from v to w through the
green set. It has cost
many edges and nodes,
so itʼs not a full example) ··· Vertices 1, … k k+2 D(k)[v, w]
64
FLOYD-WARSHALL: A DP APPROACH
D(k)[v, w] is the cost of the shortest path from v to w, s.t. all of the internal
vertices on the path are in the set of vertices {1, …, k}. To
be,
or n
Two cases to consider: vertex k is not included in that path, or it is. ot t
o be

k
k+1 k–1 n
w
v 1 3

···
··· 2 k+2
65
FLOYD-WARSHALL: A DP APPROACH
D(k)[v, w] = cost of the shortest path from v to w, s.t. all the internal vertices on the path are in the set of vertices {1,…, k}.

CASE 1: We don’t need vertex k! So, D(k)[v, w] = D(k–1)[v, w]

In this case, this means

that this path was the k
shortest before and itʼs
k+1 n
still the shortest now
1 w
v 3 k–1

2 ···
··· Vertices 1, … k–1 k+2
Vertices 1, … k
66
FLOYD-WARSHALL: A DP APPROACH
D(k)[v, w] = cost of the shortest path from v to w, s.t. all the internal vertices on the path are in the set of vertices {1,…, k}.

CASE 1: We don’t need vertex k! So, D(k)[v, w] = D(k–1)[v, w]

In this case, this means

that this path was the k
shortest before and itʼs
k+1 n
still the shortest now
1 w
v 3 k–1
In other words, allowing paths
to go through k (in addition to 2 ···
nodes 1, …, k–1) now doesnʼt
change the shortest path cost,
··· Vertices 1, … k–1 k+2
Vertices 1, … k
since it doesnʼt need to use k. 67
FLOYD-WARSHALL: A DP APPROACH
D(k)[v, w] = cost of the shortest path from v to w, s.t. all the internal vertices on the path are in the set of vertices {1,…, k}.

CASE 2: We need vertex k! So, D(k)[v, w] = D(k–1)[v, k] + D(k–1)[k, w]

If there are no negative cycles,
then the shortest path from v k
to w is simple, and it must
look like this path: k+1 n
(we also know that neither of
1 ··· w
these subpaths contains nodes v
greater than k–1.) 3
2 k–1
··· Vertices 1, … k–1 k+2
Vertices 1, … k
68
FLOYD-WARSHALL: A DP APPROACH
D(k)[v, w] = cost of the shortest path from v to w, s.t. all the internal vertices on the path are in the set of vertices {1,…, k}.

CASE 2: We need vertex k! So, D(k)[v, w] = D(k–1)[v, k] + D(k–1)[k, w]

If there are no negative cycles,
then the shortest path from v k
to w is simple, and it must
look like this path: k+1 n
(we also know that neither of
1 ··· w
these subpaths contains nodes v
greater than k–1.) 3
2 k–1 This is the shortest
This is the shortest path from v to k path from k to w
through {1, …, k–1} (remember,
sub-paths of shortest paths are
··· Vertices 1, … k–1 k+2
through {1, …, k–1}

shortest paths!) Vertices 1, … k

69
FLOYD-WARSHALL: A DP APPROACH
How do we find D(k)[v, w] using D(k–1)? Choose the minimum of these 2 cases:

CASE 1: We don’t need vertex k CASE 2: We need vertex k

k k
k+1 n k+1 n
1
v k–1 w v 1 ··· w
3
3
2 ··· 2 k–1
··· Vertices 1, … k–1 k+2 ··· Vertices 1, … k–1 k+2
Vertices 1, … k Vertices 1, … k

D(k)[v, w] = D(k–1)[v, w] D(k)[v, w]= D(k–1)[v, k] + D(k–1)[k,

w] 70
FLOYD-WARSHALL: A DP APPROACH
How do we find D(k)[v, w] using D(k–1)? Choose the minimum of these 2 cases:

This
CASE is our
1: We optimal
don’t substructure:
need vertex k We know what
CASEour subproblems
2: We arek
need vertex
(finding costs of shortest paths through a restricted set of vertices), and we
know howk to express our optimal solution in terms of thesek
subproblem
k+1
results (get the
n minimum of these two cases).
k+1 n
1
v These subproblems
k–1 are also
woverlapping:
v Memoization/caching
1 ··· can be w
3 (k–1) (k)
useful here! For example, D [k, w] can be used to help 3 compute D [v, w]
··· k–1
2 for a lot of different starting points as v! 2
··· Vertices 1, … k–1 k+2 ··· Vertices 1, … k–1 k+2
Now that we’ve settled this, we can write the algorithm!
Vertices 1, … k Vertices 1, … k

D(k)[v, w] = D(k–1)[v, w] D(k)[v, w]= D(k–1)[v, k] + D(k–1)[k,

w] 71
FLOYD-WARSHALL: A DP APPROACH
FLOYD_WARSHALL(G):
Initialize n x n arrays D(k) for k = 0,...,n
D(k)[v,v] = 0 for all v, for all k
D(k)[v,w] = ∞ for all v ≠ w, for all k
D(0)[v,w] = weight(v,w) for all (v,w) in E
for k = 1,...,n:
for pairs v,w in V2:
D(k)[v,w] = min{ D(k–1)[v,w], D(k–1)[v,k] + D(k–1)[k,w] }
return D(n)

72
FLOYD-WARSHALL: A DP APPROACH
Keeping all these n x n arrays
FLOYD_WARSHALL(G): would be a waste of space. In
practice, only need to store 2!
Initialize n x n arrays D(k) for k = 0,...,n
D(k)[v,v] = 0 for all v, for all k
D(k)[v,w] = ∞ for all v ≠ w, for all k
D(0)[v,w] = weight(v,w) for all (v,w) in E
for k = 1,...,n:
Take the minimum over our two cases!
for pairs v,w in V2:
D(k)[v,w] = min{ D(k–1)[v,w], D(k–1)[v,k] + D(k–1)[k,w] }
return D(n)

73
FLOYD-WARSHALL: A DP APPROACH
Keeping all these n x n arrays
FLOYD_WARSHALL(G): would be a waste of space. In
practice, only need to store 2!
Initialize n x n arrays D(k) for k = 0,...,n
D(k)[v,v] = 0 for all v, for all k
D(k)[v,w] = ∞ for all v ≠ w, for all k
D(0)[v,w] = weight(v,w) for all (v,w) in E
for k = 1,...,n:
Take the minimum over our two cases!
for pairs v,w in V2:
D(k)[v,w] = min{ D(k–1)[v,w], D(k–1)[v,k] + D(k–1)[k,w] }
return D(n)

Runtime: ?
74
FLOYD-WARSHALL: A DP APPROACH
Keeping all these n x n arrays
FLOYD_WARSHALL(G): would be a waste of space. In
practice, only need to store 2!
Initialize n x n arrays D(k) for k = 0,...,n
D(k)[v,v] = 0 for all v, for all k
D(k)[v,w] = ∞ for all v ≠ w, for all k
D(0)[v,w] = weight(v,w) for all (v,w) in E
for k = 1,...,n:
Take the minimum over our two cases!
for pairs v,w in V2:
D(k)[v,w] = min{ D(k–1)[v,w], D(k–1)[v,k] + D(k–1)[k,w] }
return D(n)

Runtime: O(n3)
(Better than running Bellman-Ford n times!) 75
WHAT ABOUT NEGATIVE CYCLES?
Negative cycle means there’s some v
s.t. there is a path from v to v that has cost < 0

76
WHAT ABOUT NEGATIVE CYCLES?
Negative cycle means there’s some v
s.t. there is a path from v to v that has cost < 0
FLOYD_WARSHALL(G):
Initialize n x n arrays D(k) for k = 0,...,n
D(k)[v,v] = 0 for all v, for all k
D(k)[v,w] = ∞ for all v ≠ w, for all k
D(k)[v,w] = weight(v,w) for all (v,w) in E
for k = 1,...,n:
for pairs v,w in V2:
D(k)[v,w] = min{ D(k–1)[v,w], D(k–1)[v,k] + D(k–1)[k,w]
}
for v in V:
if D(n)[v,v] < 0:
throw “NEGATIVE CYCLE!”
return D(n) 77
 n = |V|
SHORTEST-PATH ALGORITHMS m = |E|

BFS DFS DIJKSTRA BELLMAN-FORD FLOYD-WARSHALL

O(m+n) O(m+n) O(m+nlogn)* O(mn) O(n3)

Weighted Weighted Weighted

Unweighted Unweighted (weights must be (can handle (can handle
(or weights don’t matter) (or weights don’t matter)
non-negative) negative weights) negative weights)

Single source
Single source Path finding (s,t) Single source shortest paths: All pairs
shortest path Toposort (DAG!!)
shortest paths: Compute shortest shortest paths:
Compute shortest path from source s Compute
Test bipartiteness Find SCC’s
path from a source to all other nodes shortest path
Find connected Find connected s to all other between every pair
components components nodes Detect negative of nodes (v,w)
cycles