Open topic Bellman-Ford 2018 11 5 171860508@smail.nju.edu.cn 1/15
Contents 1. G s BF 2. BF 3. BF 2/15
BF G Bellman-Ford false 3/15
BF G Bellman-Ford false G c = v 0, v 1,..., v k (v 0 = v k ) k w(v i 1, v i ) < 0 i=1 true (u, v) E(G) v.d u.d + w(u, v). i v i.d v i 1.d + w(v i 1, v i ) 3/15
BF k k k v i.d v i 1 + w(v i 1, v i ) i=1 i=1 i=1 v 0 = v k k v i.d = k v i 1.d i=1 i=1 0 k w(v i 1, v i ) i=1 4/15
5/15
On the V(G) -th pass (u, v) v.d > u.d + w(u, v) v 5/15
On the V(G) -th pass (u, v) v.d > u.d + w(u, v) v v v.d v 5/15
v 3 s v 2 v 0 v 5 v 1 v 4 The original graph 6/15
v 3 s v 2 v 0 v 5 v 1 v 4 4 0 3 5 3 6 6 The original graph G after V(G) 1 passes 6/15
v 3 s v 2 v 0 v 5 v 1 v 4 4 0 3 5 3 6 6 v 3 s v 2 v 0 v 5 v 1 v 4 The original graph G after V(G) 1 passes G.π after V(G) 1 passes 6/15
v 2 v 0 v 3 v 1 v 1 v 2 the cycle v 0 v 3 v 0 s v 4 v 4 v 5 v 5 G.π after V(G) passes Visited nodes during the search 7/15
v 2 v 0 v 3 v 1 v 1 v 2 the cycle v 0 v 3 v 0 s v 4 v 4 v 5 v 5 G.π after V(G) passes Visited nodes during the search vis 7/15
BF Algorithm 1 Bellman-Ford with Negative Cycle Output 1: function Bellman-Ford-Mod(G, s, w) 2: Initialize-Single-Source(G, s) 3: for i = 1 to V(G) 1 do 4: for edge (u, v) E(G) do 5: Relax(u, v, w) 6: end for 7: end for 8: for edge (u, v) E(G) do One more pass 9: if v.d > u.d + w(u, v) then 8/15
BF Algorithm 2 Bellman-Ford with Negative Cycle Output 1: function Bellman-Ford-Mod(G, s, w) 2: Initialize-Single-Source(G, s) 3: for i = 1 to V(G) 1 do 4: for edge (u, v) E(G) do 5: Relax(u, v, w) 6: end for 7: end for 8: for edge (u, v) E(G) do One more pass 9: if v.d > u.d + w(u, v) then 10: v.π = u What happens if a V -cycle? 11: return Negative-Cycle-Aux(v) Only one cycle 12: end if 13: end for 14: return an empty vector 15: end function 8/15
BF Algorithm 3 Output the negative cycle found with node v 1: function Negative-Cycle-Aux(v) 2: let c be a vector to hold the cycle 3: let vis be an empty array of size V(G) 4: create a pointer p initially pointed at v 9/15
BF Algorithm 4 Output the negative cycle found with node v 1: function Negative-Cycle-Aux(v) 2: let c be a vector to hold the cycle 3: let vis be an empty array of size V(G) 4: create a pointer p initially pointed at v 5: while vis[p] == false do break at second visit 6: vis[p] == true mark the pointed as visited 7: p = p.π visit p s parent 8: end while 9/15
BF Algorithm 5 Output the negative cycle found with node v 1: function Negative-Cycle-Aux(v) 2: let c be a vector to hold the cycle 3: let vis be an empty array of size V(G) 4: create a pointer p initially pointed at v 5: while vis[p] == false do break at second visit 6: vis[p] == true mark the pointed as visited 7: p = p.π visit p s parent 8: end while 9: let t = p and p = p.π 10: while p t do 11: push p into c 12: end while 13: push t into c and return c 14: end function 9/15
BF incycle 10/15
BF incycle G (u, v) E(G), v.d > u.d + w(u, v) 10/15
BF incycle G (u, v) E(G), v.d > u.d + w(u, v) (a). G.π 10/15
BF incycle G (u, v) E(G), v.d > u.d + w(u, v) (a). G.π (b). G.π v π 10/15
1 Relax v { v.d < 0, v == s, v.π Nil v.d < +, o.w. 11/15
1 Relax v { v.d < 0, v == s, v.π Nil v.d < +, o.w. 2 G.π s.d = 0 G.π s 11/15
1 Relax v { v.d < 0, v == s, v.π Nil v.d < +, o.w. 2 G.π s.d = 0 G.π s G.π v.d < + G.π s.d = 0 s Relax s s 11/15
(a) G.π c = v 0, v 1,..., v k (v 0 = v k ) G.π (v k 1, v k ) 12/15
(a) G.π c = v 0, v 1,..., v k (v 0 = v k ) G.π (v k 1, v k ) v 0 = v k > v k 1 + w(v k 1, v k ) = (v k 2 + w(v k 2, v k 1 )) + w(v k 1, v k ) = k = v 0 + w(v i 1, v i ) > v 0 i=1 12/15
(b) 1 v.π s s.d = 0 13/15
(b) 1 v.π s s.d = 0 G.π s v G s v Path-relaxation property v.d = δ(s, v) (u, v) E(G), v.d > u.d + w(u, v) 13/15
(b) 1 v.π s s.d = 0 G.π s v G s v Path-relaxation property v.d = δ(s, v) (u, v) E(G), v.d > u.d + w(u, v) V(G) V(G) G.π s 13/15
Bellman-Ford O( V E ) 14/15
Bellman-Ford O( V E ) O( V ) + O( V ) = O( V ) 14/15
Bellman-Ford O( V E ) O( V ) + O( V ) = O( V ) O( V E ) 14/15
G 15/15
G s t v (s, v) (v, t) s Bellman-Ford 15/15
G v 2 s v 2 s v 3? v 1 s 0 v 3 v 1 v 0 t v 0 Unreachable Reachable s t v (s, v) (v, t) s Bellman-Ford 15/15
G v 2 s v 2 s v 3? v 1 s 0 v 3 v 1 v 0 t v 0 Unreachable Reachable s t v (s, v) (v, t) s Bellman-Ford O(2 V ) + O( V ( E + V )) = O( V E + V 2 ) 15/15
Thanks Q & A 15/15