Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley


Download 27.59 Kb.

Sana13.08.2017
Hajmi27.59 Kb.

Lecture slides by Kevin Wayne


Copyright © 2005 Pearson-Addison Wesley


http://www.cs.princeton.edu/~wayne/kleinberg-tardos

Last updated on 7/25/17 10:58 AM

4.  G

REEDY


 A

LGORITHMS

 II

‣ Edmonds branching algorithm demo


Edmonds branching algorithm demo

2

r



10

6

5



2

11

3



9

7

13



1

12

8



4

input digraph G = (V, E)

Edmonds branching algorithm demo

3

r



10

6

5



2

11

3



9

7

13



1

12

8



4

2

3



12

7

9



1

10

Phase 1:  find cheapest edge entering each node



Edmonds branching algorithm demo

4

r



0

4

3



0

1

0



0

0

4



0

0

7



1

2

3



12

7

9



1

10

Phase 1:  replace costs with reduced costs



Edmonds branching algorithm demo

5

r



0

4

3



0

1

0



0

0

4



0

0

7



1

Phase 1:  find 0-cost directed cycle C and contract

r

4



3

0

1



0

0

7



1

Edmonds branching algorithm demo

6

Phase 2:  digraph G'

4

3

0



1

0

0



7

1

r



Edmonds branching algorithm demo

7

Phase 2:  find cheapest edge entering each node

4

3

0



1

0

0



7

1

r



1

0

0



0

Edmonds branching algorithm demo

8

Phase 2:  replace cost with reduced costs

3

2

0



1

0

0



7

0

r



1

0

0



0

Edmonds branching algorithm demo

9

Phase 2:  find 0-cost directed cycle and contract

3

2

0



1

0

0



7

0

r



3

2

0



1

r


Edmonds branching algorithm demo

r

10



Phase 3:  digraph G''

3

2



0

1


Edmonds branching algorithm demo

r

11



Phase 3:  find cheapest edge entering each node

3

2



0

1


Edmonds branching algorithm demo

r

12



Phase 3:  it's an arborescence!

3

2



0

1


Edmonds branching algorithm demo

r

13



Phase 2':  uncontract node and take all but one edge of cycle

3

2



0

1

3



2

0

1



0

0

7



0

r

don't take 



this edge

Edmonds branching algorithm demo

14

Phase 1':  uncontract node and take all but one edge of cycle

r

r

don't take 



this edge

Edmonds branching algorithm demo

15

stop:  no more nodes to uncontract

r


Edmonds branching algorithm demo

16

min-cost arborescence

r

10

6



5

2

11



3

9

7



13

1

12



8

4


Do'stlaringiz bilan baham:


Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2017
ma'muriyatiga murojaat qiling