Shortest paths in graphs
Based on slides by David Kauchak
Shortest paths
What is the shortest path from a to d?
BD
A
CE
Shortest paths
BFS
BD
A
CE
Shortest paths
What is the shortest path from a to d?
B2D 3
3 1
CE 4
A
1
2
Shortest paths
We can still use BFS * . but it would be very inefficient.
B2D 3
3 1
CE 4
A
1
2
Shortest paths
We can still use BFS
B2D 3
132 A
CE 4
BD
CE
A
1
Shortest paths
We can still use BFS
BD
A
CE
Shortest paths
What is the problem?
BD
A
CE
Shortest paths
Running time is dependent on the weights
B 2
B 100
50 4C 200C
A
1
A
Shortest paths
B 100
50 200 C
B
A
A
C
Shortest paths
B
A
C
Shortest paths
B
A
C
Shortest paths
Nothing will change as we expand the frontier until we’ve gone out 100 levels
B
A
C
Coop
ofu ; nodes are inKK
a distEu]+ weightcu, u ) distEv]= olistEu]+ weightcu.
–
–
are 20
.
mode is marked known Ckeptin set for each mode n , w e keep a tentative distance
–
each
or unknown
DIJKSTRA’S ALGORITHM
all
weights
d is-t Tu ] = weight of the shortest path from s to x ,
using only
If
shortest → path5
→4
.
x E k ALGORITHM :
d ist
⇐
IN
eight of ,
.-
–
initialization :
4at
,,
setS.
–
step
add to K the
distr] for all neighbors n,
o 5→O-so→ →4
nodes in KK .
d
,
each
update
till allthe update Cu ) 1
continue
if
( dist Ev]
,
.
node v me smallest
dist-43.
in –
#t K
.
—
known
nodes
.
Ex]
K = empty olist-63=0 distaffs for all
Dijkstra’s algorithm
(we
“”
keep unknown
⇒-K
nodes in tasty HEAP) }updatecu )
Dijkstra’s algorithm
Dijkstra’s algorithm
prev keeps track of the shortest path
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Sao
t.
V-
to. ¥•4¥↳¥
← K
→
dis ,
K
567 * x x x x no
0 Yikibiyisixgi, y 43si
ViO l i
I385 :1¥’÷-÷fe
O 2 3 1 38 5 Y i 4 i Y ,y Y y Y 4 V 3 Y y
“1144142 us Vg Y ,
,
42,43,V3 Vg Vy ,
23 YiYYyYV4k3Y4
Y
,
ily
O
,
IG5 Hilly ” 2,113,45 YG O 2 3 3
,
41144 Nz 43,45 47,46 ,,
Y, YYgYYy’4”4
ere. l234
–
,
–
—-
x
RUNTIME OF
DIJKSTRA’S ALGORITHM
Implementation using an array for V – K : O (lyft El)
t. ↳ time to scan the
time for the updates
–
done
array and firedruin
till times
Implementation
M IN
Find rain DeleteTain :
using a
takes O(logH1), is done
:
update
TOTAL :
1111 times done E) times
:
takes 0 ( login) , is ONYITIED. logN1 )
HEAP for takes OG), is done 171 times
V-K
.
DIJKSTRA’s ALG : PROOF O F CORRECTNESS
Vi,Vz,– – ,Vi,.-.,4hbetheorderinwhichmodesenterK. Att stepi cueherexi entersK)# We’llshowbyinduction.
Let
(a)Forevery yEV
(b)
Proof byinduction on
(i- II→ in Shonan Ca) :
dist i] weight i:
of
a shortest
path
CASE i :
Then
– .
—
CASE 2 : thorny
*
else
5→
weight ofthis path.
=
.
Vi
→ 4
V i E
( shortest restricted path 5 possibility is
→
→4)
-K ist #
–
ofashortestrestricted o→4
5→o→
all ink
weight →
, d Ex]= -.
.
is ,
E ( shortest restricted path5 → –
(5→.– →→4anddist-43=
—→→
…-7→4
But theene weight shortest5→ . . – → 4 t distTv3 . impossible.
checkitistrue.
) dist-43 does not change at step i .
Proof ( continuation )
:
(b)
Supposethereis apath5→-
K
Idea
. to go outofKs
be first node outof *
→
dist i] = weight of a shortest path .
– – → of
-5 → restricted
.–
i3
this
= distExitweight(* →
weight e dist Ivi]
.
→→J→ HE
—
path
distal > weight of #
So
dist ElITS distant
IMPOSSIBLE because atstepi,we pickYi with smallest distE3
HH
Let
→4→
4
.
path
.
\
.–
→Yi)
.
3
A
1
B3D q
1
1 2
CE 4
dist-43 is correct
has shortest restricted
← iolist . .
At
i
–
”
has
to be
shortest distance
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
found
i
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
3 BD
3
112
ANOTHER
EXAMPLE
A
1
CE 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
3 BD
3
0
A
1
Heap
A0 B C D E
112
CE 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
3 BD
3
0
A
1
Heap
B C D E
1 1
2
CE 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
3 BD
3
0
A
1
Heap
B C D E
1 1
2
CE 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
3 BD
3
0
A
1
Heap
C1
B D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
3 BD
3
0
A
1
Heap
C1
B D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
33 BD
3
0
A
1
Heap
C1 B3 D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
33 BD
3
0
A
1
Heap
C1 B3 D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
33 BD
3
0
A
1
Heap
B3 D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
33 BD
3
0
A
1
Heap
B3 D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
33 BD
3
0
A
1
Heap
B3 D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
23 BD
3
0
A
1
Heap
B2
D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
23 BD
3
0
A
1
Heap
B2 D E
1 1
2
C1E 4
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
23 BD
3
0
A
1
Heap
B2
E5
D
1 1
2
C1E 4
5
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
23 BD
3
0
A
1
Heap
B2 E5 D
Frontier?
1 1
2
C1E 4
5
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
3
0
A
1
23 BD
1 2
Heap
B2 E5 D
All nodes reachable from starting node within a given distance
1
C1E 4
5
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
Heap
E3 D5
235 BD
3
0
A
1
1 1
2
C1E 4
3
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
Heap D5
235 BD
3
0
A
1
1 1
2
C1E 4
3
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
Heap
235 BD
3
0
A
1
1 1
2
C1E 4
3
K = vertices out of the heap
dist[v]= shortest distance from s to v using along the path only vertices in K
Heap
0
A
1
235 BD
1 1
C1E
3
¥8 GRAPHS What about Dijkstra’s on…?
with
negative
weights
?
DOESNOT theORK
1 1BD
!
A
C
5 -10
E
10
BELLMAN
– FORD
– weights can also be co ; but no negative cycle.
alg . Bounding the distance
Another invariant: For each vertex v, dist[v] is an upper bound
on the actual shortest distance • startoffat
– 5→4
• onlyupdatethevalueifwefindashorterdistance
An update procedure
dist[v] min{dist[v], dist[u] w(u, v)}
ETI
u
.-
→
SKID
Bounding the distance
Another invariant: For each vertex v, dist[v] is an upper bound on the actual shortest distance
• startoffat
• onlyupdatethevalueifwefindashorterdistance
An update procedure
dist[v] min{dist[v], dist[u] w(u, v)}
dist[v] min{dist[v], dist[u] w(u, v)} UEV
Can we ever go wrong applying this update rule?
• We can apply this rule as many times as we want and will never underestimate dist[v]
When will dist[v] be right?
• If u is along the shortest path to v and dist[u] is correct
dist[v] min{dist[v], dist[u] w(u, v)} VEY
dist[v] will be right if u is along the shortest path to v and dist[u] is correct
Consider the shortest path from s to v
s p1 p2 p3 pk v
dist[v] min{dist[v], dist[u] w(u, v)} dist[v] will be right if u is along the shortest path to v
and dist[u] is correct
What happens if we update all of the vertices with the above update?
s p1 p2 p3 pk v
dist[v] min{dist[v], dist[u] w(u, v)} UEV
dist[v] will be right if u is along the shortest path to v and dist[u] is correct
What happens if we update all of the vertices with the above update?
s p1 p2 p3 pk v
correct
dist[v] min{dist[v], dist[u] w(u, v)} U EV
dist[v] will be right if u is along the shortest path to v and dist[u] is correct
What happens if we update all of the vertices with the above update?
s p1 p2 p3 pk v
correct correct
dist[v] min{dist[v], dist[u] w(u, v)} VEY
dist[v] will be correct (meaning minimal) if u is along the shortest path to v and dist[u] is correct
Does the order that we update the vertices matter?
s p1 p2 p3 pk v
correct correct
dist[v] min{dist[v], dist[u] w(u, v)} UEV
dist[v] will be right if u is along the shortest path to v and dist[u] is correct
How many times do we have to do this for vertex pi to have the correct shortest path from s?
• i times
s p1 p2 p3 pk v
dist[v] min{dist[v], dist[u] w(u, v)} UEV
dist[v] will be right if u is along the shortest path to v and dist[u] is correct
How many times do we have to do this for vertex pi to have the correct shortest path from s?
• i times
s p1 p2 p3 pk v
correct correct
dist[v] min{dist[v], dist[u] w(u, v)} VEY
dist[v] will be right if u is along the shortest path to v and dist[u] is correct
How many times do we have to do this for vertex pi to have the correct shortest path from s?
• i times
s p1 p2 p3 pk v
correct correct correct
dist[v] min{dist[v], dist[u] w(u, v)} well
dist[v] will be right if u is along the shortest path to v and dist[u] is correct
What is the longest (vertex-wise) the path from s to any node v
can be? AaT##FiWT#-
• |V| – 1 edges/vertices A longer path
s p1 p2 p3
contains a cycle
c a n b!e r e m o v e d . pk v
correct
correct
correct
correct
… c . e n s i g n s: O
.— .–
9→ 8→ ×→8→. –
, which
→
4
Bellman-Ford algorithm
Bellman-Ford algorithm
Initialize all the distances
do it |V| -1 times
iterate over all edges/vertices and apply update rule
Bellman-Ford algorithm
check for negative cycles
Negative cycles
What is the shortest path from a to e?
1 1BD
A
10
C
5 -10
E 3
Bellman-Ford algorithm
Bellman-Ford algorithm
S 10 A 81
How many edges is the shortest path from s to:
G-4 BA: 2
1
F
-1
-2
1
C
3
ED -1
Bellman-Ford algorithm
S 10 A 81
How many edges is the shortest path from s to:
G-4 BA:3 2
1
F
-1
-2
1
C
3
ED -1
Bellman-Ford algorithm
S 10 A 81
How many edges is the shortest path from s to:
G-4 BA:3 2
1
F
-1
1
-2 C B:
3
ED -1
Bellman-Ford algorithm
S 10 A 81
How many edges is the shortest path from s to:
G-4 BA:3 2
1
F
-1
1
-2 C B:5
3
ED -1
Bellman-Ford algorithm
S 10 A 81
How many edges is the shortest path from s to:
G-4 BA:3 2
1
F
-1
1
-2 C B:5
ED -1
3
D:
Bellman-Ford algorithm
S 10 A 81
How many edges is the shortest path from s to:
G-4 BA:3 2
1
F
-1
1
-2 C B:5
3
D: 7
ED -1
Bellman-Ford algorithm
0
S 10 A 81
G-4 B
Iteration: 0
1
F
-1
2
-2
3
1
C
ED
-1
Bellman-Ford algorithm
0 10
S 10 A 81
8G-4 B 2
Iteration: 1
1
F
-1
1
-2
3
C
ED
-1
Bellman-Ford algorithm
0 10
S 10 A 81
8G-4 B 2
Iteration: 2
1
F
1
9
3 ED
-1
-1
-2
C
12
Bellman-Ford algorithm
05
S 10 A 81
-4
Iteration: 3
A has the correct distance and path
8
9
G
F
2
10
B
C
1
1
-2
3 ED
-1
-1
8
Bellman-Ford algorithm
05
S 10 A 81
6
8G-4 B 2
Iteration: 4
9
1
F
-2
1
C
11
3 ED
-1
-1
7
Bellman-Ford algorithm
05
S 10 A 81
-4
Iteration: 5
B has the correct distance and path
8
9
G
F
2
5
B
C
14
1
1
-2
7
3 ED
-1
-1
7
Bellman-Ford algorithm
05
S 10 A 81
5 8G-4 B
Iteration: 6
1
F
2
-2
1
C
10
6
9
3 ED
-1
-1
7
Bellman-Ford algorithm
05
S 10 A 81
-4
5
Iteration: 7
D (and all other nodes) have the correct distance and path
8
9
G
F
2
B
1
1
-2
C6 3
9
-1
ED
-1
7
Correctness of Bellman-Ford
Loop invariant:
Correctness of Bellman-Ford
Loop invariant: After iteration i, dist[v] = weight of a shortest path from s to v of length i edges or less.
Runtime of Bellman-Ford
O(|V| |E|)
Runtime of Bellman-Ford
Can you modify the algorithm to run faster (in some circumstances)?
Single source shortest paths
All of the shortest path algorithms we’ve looked at today are call “single source shortest paths” algorithms
Why?
All pairs shortest paths – shortest from any node u to any node v
Simple approach
• Call Bellman-Ford |V| times , time: O(|V|2 |E|)
• Call Dijkstra |V| times , time: |V| × 𝑡𝑖𝑚𝑒 𝐷𝑖𝑗𝑘𝑠𝑡𝑟𝑎 = O(|V| |E| log |V|) with minHEAP,
O(|V|3 ) with array
Floyd-Warshall – Θ(|V|3)
Johnson’s algorithm – O(|V|2 log |V| + |V| |E|) (we will not cover)
Floyd-Warshall
• Dynamicprogrammingalgorithm
• Labelthenodes1,2,…,n
• Subproblem: 𝑑 𝑖, 𝑗 = weight of shortest path from i to j that is allowed to go only through 1,…k • Initialization: 𝑑 𝑖, 𝑗 = W[i,j] (weight of the edge (i,j))
• Recurrence
𝑑 𝑖,𝑗 =min(𝑑 𝑖,𝑗 ,𝑑 𝑖,𝑘 +𝑑 𝑘,𝑗 )
Why: going from i to j, either we do not use k, and then the best is 𝑑 𝑖, 𝑗
or we use k, and then the best is 𝑑 𝑖,𝑘 + 𝑑 𝑘,𝑗
(Observation: from i to k, or from k to j, it is not advantageous to pass
through k, because weight[shortest path from k to k] ≥ 0) So: we compute the 𝑑 𝑖, 𝑗 values, the 𝑑 𝑖, 𝑗 values, …, 𝑑 𝑖, 𝑗 values
1 → -O –
o→8
so→–→ ” stepping stones ” E
Sh a K) –
Floyd-Warshall pseudocode
Improvement: we don’t need a new matrix, because 𝑑 𝑖, 𝑘 = 𝑑 𝑖, 𝑘 and
𝑑 𝑘,𝑗 =𝑑 𝑘,𝑗
At the same time, we can compute the matrix of predecessors 𝜋 𝑖, 𝑗 = predecessor of j on the shortest path from i to j allowed to go only through 1, … , k
FLOYD- IN ARSHALL
Input : G — CHE) weighted graph; n o negative cycles
for all if Elli. – ins dei, D= Weisz]
for k frow I to n for i from 1 to n
for J from 1 to mo] lting
,dEiik3xdTkD3 )
— min letting RUNTIME : 01ns).
.
1I
.TT. 3
i.
t:* : ne:÷÷÷÷s
* .
”
“”
f÷÷÷ ÷÷÷÷i
‘s
=/: : :
:: i: :
‘so ) :