Dynamic Programing
Floyd-Warshall’s All-Pairs Shortest Paths
Algorithm
2021-02-10 CSC373 Winter 2021 – Sam Toueg 1
All-Pairs Shortest Paths
• Problem ØInput:
Ø,!”=∞if -,. ∉*
ØOutput: length of a shortest path from each node ! to each node %
First idea: Run Bellman-Ford’s single-source shortest paths algorithm for every source ! ∈ # (i.e., run it $ times).
⇒”#$ timeforeachsource1 ⇒”#$! time
⇒” $” ifthegraph4isdense
Directed graph & = (#, *) with no negative-length cycle Edge lengths ,!” on each edge -, .
2021-02-10 CSC373 Winter 2021 – Sam Toueg 3
All-Pairs Shortest Paths • ! = {1, 2, … , (}, 1 ≤ +, , ≤ (
!
• – is an + ⤳ , path if every intermediate node in – is ≤ /
Ø i.e., 7 can use only nodes in {1, 2, … , =} in the “middle’’
7 1 24
5 3 6 3
5
7 ⤳ 3 path? ✅
5
2 ⤳ 3 path? ❌
2021-02-10
CSC373 Winter 2021 – Sam Toueg
4
All-Pairs Shortest Paths
• ! = {1, 2, … , (}, 1 ≤ +, , ≤ ( !
• – is an + ⤳ , path if every intermediate node in – is ≤ / Ø i.e., 7 can use only nodes in {1, 2, … , =} in the “middle’’
Ø = = 0 : no intermediate node is allowed
• Subproblem: 89: ;, <, = = length of shortest (simple) ; ⤳ < path
!
• Consider a shortest + ⤳ , path -
!-1 Case1:node=∉9⇒9isan;⤳
2021-02-10
“7DE,F,= = 1
0 otherwise
if = = 0 and (E = F or (E, F) ∈ Z)
CSC373 Winter 2021 – Sam Toueg 13
Detecting Negative Length Cycles
• We can use Floyd-Warshall algorithm to detect negative cycles •Claim4:!hasanegativecycle⟺∃$∈&,()* $,$,+ <0 • Proof of Claim 4:
First prove the following facts (see Assignment 3)
At the end of iteration ! of the outer loop of the F-W algorithm:
!
(1) 89:(;, <, =) is the length of some ; ⤳ < path
!
(2) 89:(;, <, =) ≤ length of every simple ; ⤳ < path
Then use (1) and (2) to prove Claim 4 • Use Claim 4 to detect negative cycles
2021-02-10 CSC373 Winter 2021 - Sam Toueg 14
Difference Constraints
2021-02-10 CSC373 Winter 2021 - Sam Toueg 1
Difference Constraints
• Variables: !!,..., !"
• Constraints: # constraints of the form !# − !$ ≤ &$#, &$# ∈ R
• Problem: Are these constraints satisfiable?
Example:
(:
!!−!" !#−!" !$−!" !$−!! !#−!$
≤ −4 ≤ 3
≤ −2 ≤ 1 ≤ 1
• Is)satisfiable?
Ø Yes! (!!, !%, !&, !') = (0, −4, −2, −3)
• How can we solve this ``Difference Constraints’’ problem?
2021-02-10 CSC373 Winter 2021 - Sam Toueg 3
Difference Constraints
• Given a set ) of D-Cs, define this weighted directed graph 2( = 3, 4 :
Ø For each variable !$: put node 6$ in 3
Ø For each constraint !# − !$ ≤ &$#: put weighted edge
+%& * *% &
in 4
!!−!" !#−!" !$−!" !$−!! !#−!$
≤ ≤
−4 3
−2
1 *$
(:
,':
*" −4 *!
≤ −2 3 ≤ 1
1
≤
1 *#
2021-02-10
CSC373 Winter 2021 - Sam Toueg
4
Difference Constraints
• Given a set ) of D-Cs, define this weighted directed graph 2( = (3, 4):
Ø For each variable !$: put node 6$ in 3 +%& *
Ø For each constraint !# − !$ ≤ &$#: put weighted edge *% & in 4
Theorem: ) is satisfiable ⇔ 2( has no negative-weight cycle
Proof: (⇒) By contradiction. !!" !"#
...
!$! → *( → *"
• Suppose ) is satisfiable but 2( has negative-weight cycle:*" → *! → *#
• So ) contains the constraints and ∃ values for ! , ! , ... , ! that satisfies them
• Since ) is satisfiable, ∃ values for !!, !%, ... , !) sa"tisf!ying t(he following constraints: !! −!" ≤ +"!
+ !#−!! ≤ +!# + ⋮⋮⋮⋮⋮
+ !(−!()" ≤ +()"( + + !"−!( ≤ +(" +
(!!+!#+ ...+!(+ !")−(!"+!!+ ...+!()"+ !()=0≤weiighttofftthecyclle<00 contradiction!
2021-02-10 CSC373 Winter 2021 - Sam Toueg
5
• Given a set ) of D-Cs, define this weighted directed graph 2( = 3, 4 :
Ø For each variable !$: put node 6$ in 3 +%& Ø For each constraint !# − !$ ≤ &$#: put weighted edge *%
*& in 4
Theorem: ) is satisfiable ⇔ 2( has no negative-weight cycle
Proof:(⇐)Suppose2( hasnonegative-weightcycle
• Constructgraph2(* =(3 ∪ F ,4∪ F,6 : 6∈3 )withweight F,6$ =0 ∀6$ ∈3
+%&
,*: (: '
'0−4 !*% !!−!" ≤ −4 0 *" *! !"=0 %
!#−!" ≤ 3 ; 3 −2 1 !!=−4 ; !$−!"≤−2 0* *!#=−2
!$−!!≤1 #1$!$=−3 !&* !# − !$ ≤ 1 0 !& ≤ !% + +%& &
* !& − !% ≤ +%& ! • 2( has no negative-weight cycle ⇒ 2( has no negative-weight cycle
• So 2(* has a shortest path F ⤳ 6$, for every node 6$
• ∀I,set!$ tobetheweightoftheshortestpathF⤳6$ in2(*
• These !$ values satisfy every constraint in ) because of the triangle inequality! 2021-02-10 CSC373 Winter 2021 - Sam Toueg 6
DC Solver
DC_SOLVER (M) () : # difference constraints over N variables)
1. 2. 3. 4. 5. 6. 7. 8.
construct the corresponding weighted graph 2(* run Bellman-Ford on 2(* with source F
if Bellman-Ford finds a negative-weight cycle then
Q(# + N)
Q(N · #)
return “) is unsatisfiable”
else \* Bellman-Ford found a shortest-path from F to every other node *\
for I = 1 to N do
!$ ← weight of shortest path from F to 6$ found by Bellman-Ford
return !!, !%, ... , !" Running Time: Q(N · #)
2021-02-10 CSC373 Winter 2021 - Sam Toueg 7
Johnson’s All-Pairs Shortest Paths Algorithm
2021-02-10 CSC373 Winter 2021 - Sam Toueg 1
All-Pairs Shortest Paths • Input:weightedgraph!=($,&)
• To compute all-pairs shortest paths:
Ø Run Dijsktra ( times Ø Run BF ( times
Ø Run FW
+(( , - , log () but does not work with negative-weight edges! +(( , ( , -)
+((!)
Dijsktra is the fastest for a sparse !, for example:
Ø when each node has a constant degree, so ! = #(%), or
Ø when each node has a #(log %) degree, so ! = #(% log %)
•
• Whatif!=($,&)hasnegative-weightedges(withnonegativecycles)?
• TouseDijsktra:re-weighteachedgetomakeedge-weights≥0
re-weight: +2
Naïve attempt: add same positive constant (here: +2) to every weight
4 2 +
1
3
-2 0
*
Shortest + ⤳ * path before this reweight Shortest + ⤳ * path after this reweight
Bad: his reweight changed the shortest path!
2021-02-10
CSC373 Winter 2021 - Sam Toueg
2
• Input:weightedgraph!=($,&)
• To compute all-pairs shortest paths:
Ø Run Dijsktra ( times Ø Run BF ( times
Ø Run WF
+(( , - , log () +(( , ( , -)
+((!)
but does not work with negative-weight edges!
1
All-Pairs Shortest Paths
Dijsktra is the fastest for a sparse !, for example:
Ø when each node has a constant degree, so ! = #(%), or
Ø when each node has a #(log %) degree, so ! = #(% log %)
•
• Whatif!=($,&)hasnegative-weightedges(withnonegativecycles)?
• TouseDijsktra:re-weighteachedgetomakeedge-weights≥0 in a way that preserves the shortest paths!
+
2 -2 1
But how? Johnson’s idea...
*
2021-02-10
CSC373 Winter 2021 - Sam Toueg 3
All-Pairs Shortest Paths
• Assign to each node 1 a node-weight 2" . Use node-weights to re-weight edges: • Original edge-weight function 3: & → R
• Newedge-weightfunction 3′:&→Rsuchthat3′(1,8)=3(1,8)+2"−2# Lemma:Let:=1;$...;% 8beanypathfrom1to8,then3′(:)=3(:)+2"−2# Proof:
3′ 1,;$ = 3(1,;$) +2"−2&! + 3′(;$,;')= 3(;$,;')+2&! −2&"
⋮
+3′;%,8 =3(;%,8) +2&#−2#
3): =3(:)+2"−2#
• Everypath:from1to8hasdecreased/increaseditsweightbythe
same amount, 2" − 2#
• Hence:3′preserveseveryshortestpath!
2021-02-10 CSC373 Winter 2021 - Sam Toueg 4
All-Pairs Shortest Paths
• Assign to each node 1 a node-weight 2" . Use node-weights to re-weight edges:
• Original edge-weight function 3: & → R
• Newedge-weightfunction 3′:&→Rsuchthat3′(1,8)=3(1,8)+2"−2# Lemma:Let:=1;$...;% 8beanypathfrom1to8,then3′(:)=3(:)+2"−2#
To use Dijkstra’s algorithm, we want the new edge weights 3′ to be non-negative • Soforeach 1,8 ∈&,wewant:3) 1,8 ≥0
⟺31,8 +2"−2#≥0
⟺ 2# − 2" ≤ 3(1, 8)
• Soforeach 1,8 ∈&,wewant:2# −2" ≤3 1,8 (*)
• These are D-C constraints on the variables 2" for 1 ∈ $ J
• ⇒ find values for the ( variable 2" that satisfy the - D-C constraints (*)
2021-02-10 CSC373 Winter 2021 - Sam Toueg 5
Johnson’sAll-PairsShortestPathsAlgoonWeightedGraph!= #,%
B = ∅ /* set of linear constraints of the form 2# − 2" ≤ 3(1,8) */ for each 1,8 ∈ & do
B=B∪ {2#−2"≤3(1,8)}
F ← DC−Solver B /* find values of 2" that satisfy all constraints in B */ +( ( , -) if F = “unsatisfiable” do return “undefined SPs” /* ! has negative-weight cycles! */
else
/*F=listof2" valuesforall1∈$ */ for each 1,8 ∈ & do
3′ 1,8 =3 1,8 +2"−2# /*note:3′ 1,8 ≥0*/ for each 1 ∈ $ do
run Dijkstra on ! with new weights 3) and source node 1 +( ( , - , log () to compute J′(1, 8) for every node 8
for each 1 ∈ $ do
for each 8 ∈ $ do
return J
J1,8 =J′(1,8)+2#−2"
Runningtime: +((,-,log() 2021-02-10 CSC373 Winter 2021 - Sam Toueg 6