Open topic Bellman-Ford算法与负环

Size: px

Start display at page:

Download "Open topic Bellman-Ford算法与负环"

感璇国
5 years ago
Views:

1 Open topic Bellman-Ford @smail.nju.edu.cn 1/15

2 Contents 1. G s BF 2. BF 3. BF 2/15

3 BF G Bellman-Ford false 3/15

4 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

5 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

6 5/15

7 On the V(G) -th pass (u, v) v.d > u.d + w(u, v) v 5/15

8 On the V(G) -th pass (u, v) v.d > u.d + w(u, v) v v v.d v 5/15

9 v 3 s v 2 v 0 v 5 v 1 v 4 The original graph 6/15

10 v 3 s v 2 v 0 v 5 v 1 v The original graph G after V(G) 1 passes 6/15

11 v 3 s v 2 v 0 v 5 v 1 v 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

12 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

13 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

14 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

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

16 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

17 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

18 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

19 BF incycle 10/15

20 BF incycle G (u, v) E(G), v.d > u.d + w(u, v) 10/15

21 BF incycle G (u, v) E(G), v.d > u.d + w(u, v) (a). G.π 10/15

22 BF incycle G (u, v) E(G), v.d > u.d + w(u, v) (a). G.π (b). G.π v π 10/15

23 1 Relax v { v.d < 0, v == s, v.π Nil v.d < +, o.w. 11/15

24 1 Relax v { v.d < 0, v == s, v.π Nil v.d < +, o.w. 2 G.π s.d = 0 G.π s 11/15

25 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

26 (a) G.π c = v 0, v 1,..., v k (v 0 = v k ) G.π (v k 1, v k ) 12/15

27 (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

28 (b) 1 v.π s s.d = 0 13/15

29 (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

30 (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

31 Bellman-Ford O( V E ) 14/15

32 Bellman-Ford O( V E ) O( V ) + O( V ) = O( V ) 14/15

33 Bellman-Ford O( V E ) O( V ) + O( V ) = O( V ) O( V E ) 14/15

34 G 15/15

35 G s t v (s, v) (v, t) s Bellman-Ford 15/15

36 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

37 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

38 Thanks Q & A 15/15

正文封面.PDF

正文封面.PDF (1999 ) 1999 1 1 1999 12 31 1 38 2 38 3 38 4 38 5 38 6 38 7 38 8 38 9 38 10 38 11 38 12 38 13 38 14 38 15 38 16 38 1 2 17 38 3.6%2.16% 13.56%3.12% 10%6.25% 10%5.88% 10%3.70% 1.10% 12.50% 13.13% 12.13%