Caminho M nimo de Fonte nica em Grafos com Pesos Negativosprofessor.ufabc.edu.br/~leticia.bueno/classes/teoriagrafos/materiais… · vértices: algoritmo de Floyd-Warshall em tempoO(n3)

Caminho Mínimo de Fonte Única emGrafos com Pesos Negativos

Letícia Rodrigues Bueno

UFABC

Problemas de Caminho Mínimo

• Caminho mínimo de fonte única: algoritmo de Dijsktra;



• Caminho mínimo de destino único: inverta a direçãodas arestas e aplique algoritmo de Dijstra;




• Caminho mínimo entre quaisquer vértices u e v :algoritmo de Dijsktra;





• Caminho mínimo em grafos com pesos negativos:algoritmo de Bellman-Ford;





• Caminho mínimo em grafos com pesos negativos:algoritmo de Bellman-Ford;

• Caminho mínimo de todos os vértices para todos osvértices: algoritmo de Floyd-Warshall em tempo O(n3).

Caminho Mínimo em Grafos com Pesos Negativos

• pode haver arestas com pesos negativos;



• se não há ciclo de peso negativo acessível a partir daorigem:



• se não há ciclo de peso negativo acessível a partir daorigem: algoritmo de Dijsktra ;



• se não há ciclo de peso negativo acessível a partir daorigem: algoritmo de Dijsktra ;

• Exemplo de ciclo de peso negativo:

0

0

0

0

0

0

s

a b

gdc

e f

0

h i

j

-4

3

5

2

6

-3

3

-6

4

8

7

2

3-8−∞

∞

∞∞


• E se adicionarmos uma constante ao peso de cadaaresta?

a

b

c

d

4

6

-9

2



a

b

c

d

13

15

0

11

a

b

c

d

4

6

-9

2mais 9



a

b

c

d

13

15

0

11

a

b

c

d

4

6

-9

2mais 9custo:1

custo:2



a

b

c

d

13

15

0

11

a

b

c

d

4

6

-9

2mais 9custo:1 custo:28

custo:11custo:2


• Algoritmo de Bellman-Ford:

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞

∞



6

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞

∞



6

7

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=1

∞

∞



6

7

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-4

i=1

∞

∞



6

7

11

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2

∞



6

7

11

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2

∞



6

7

11

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

11

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-40

i=2



6

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-4

i=2



2

7

4

2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-4

i=3



2

7

4

-2

s

t x

y z

0

6

7

5

-2

7

9

2 8

-3

-4

i=4

Caminho mínimo de fonte única: algoritmo de Bellman-Ford

1 relaxa(u, v):2 se v.d > u.d + p(u, v) então3 v.d = u.d + p(u, v)4 v.p = u

5

u v2 7

5

u v2 9

Relaxa(u,v)

(a)

5

u v2 6

5

u v2 6

Relaxa(u,v)

(b)

Complexidade do algoritmo de Bellman-Ford

1 bellman-ford(G, s):2 para u em V(G) faça3 u.d = ∞

4 u.p = None5 s.d = 06 s.p = s7 para i=1 a n-1 faça8 para ∀(u,v) ∈ E(G) faça9 relaxa(u, v)

10 para ∀(u,v) ∈ E(G) faça11 se v.d > u.d + p(u,v) então12 retorne false;13 retorne true;





Análise da complexidade:






• laço linha 2: O(n);















• laço linha 8: O(n · m);









• laço linha 10: O(m);









• laço linha 10: O(m);

• Complexidade total:O(n · m) que é maiorque O((n + m) log n)(Dijkstra);

Corretude do algoritmo de Bellman-Ford

• O problema tem subestrutura ótima: um caminhomínimo entre dois vértices contém outros caminhosmínimos em seu interior.

Aplicação do algoritmo de Bellman-Ford: Arbitragem

USD CAD AUD BRL ILS GBP EURUSD 1 1,11 1,12 2,43 3,73 0,61 0,78CAD 0,89 1 1,00 2,18 3,35 0,55 0,70AUD 0,89 0,99 1 2,16 3,32 0,55 0,69BRL 0,41 0,45 0,46 1 1,53 0,25 0,32ILS 0,26 0,29 0,30 0,65 1 0,16 0,20

GBP 1,61 1,79 1,81 3,93 6,03 1 1,26EUR 1,27 1,42 1,43 3,10 4,76 0,78 1

USD = dólar dos EUACAD = dólar canadenseAUD = dólar australianoBRL = real BrasilILS = shekel (Israel)GBP = libra esterlina (Reino Unido)EUR = euro

Cotação: 29/10/2014


USD

BRL

CAD AUD

ILS

GBP

EUR

1,11

1,12

2,43 0,20

0,61

0,78

0,89

1,00

2,183,350,

550,70

0,89

0,99

2,16

3,32

0,55

0,69

0,41

0,45

0,46

1,53

0,250,32

0,26

0,30

0,29

0,65

0,16

1,61

1,79

1,81

3,93

6,03

1,261,27

1,42 1,43

3,10 4,76

0,78

3,73


USD

BRL

CAD AUD

ILS

GBP

EUR

1,11

1,12

2,43 0,20

0,61

0,78

0,89

1,00

2,183,350,

550,70

0,89

0,99

2,16

3,32

0,55

0,69

0,41

0,45

0,46

1,53

0,250,32

0,26

0,30

0,29

0,65

0,16

1,61

1,79

1,81

3,93

6,03

1,261,27

1,42 1,43

3,10 4,76

0,78

3,73

Lucro:se produto dos pesos do ciclo > 1


USD

BRL

CAD AUD

ILS

GBP

EUR

1,11

1,12

2,43 0,20

0,61

0,78

0,89

1,00

2,183,350,

550,70

0,89

0,99

2,16

3,32

0,55

0,69

0,41

0,45

0,46

1,53

0,250,32

0,26

0,30

0,29

0,65

0,16

1,61

1,79

1,81

3,93

6,03

1,261,27

1,42 1,43

3,10 4,76

0,78

3,73

Lucro:0,99138


USD

BRL

CAD AUD

ILS

GBP

EUR

1,11

1,12

2,43 0,20

0,61

0,78

0,89

1,00

2,183,350,

550,70

0,89

0,99

2,16

3,32

0,55

0,69

0,41

0,45

0,46

1,53

0,250,32

0,26

0,30

0,29

0,65

0,16

1,61

1,79

1,81

3,93

6,03

1,261,27

1,42 1,43

3,10 4,76

0,78

3,73

Lucro:0,97769


Observe que


Observe quen1 × n2 × . . . × nm > 1



se e somente se



se e somente se1n1

×1n2

× . . .×1

nm< 1.



se e somente se1n1

×1n2

× . . .×1

nm< 1.

Aplicando log nos dois lados da desigualdade:



se e somente se1n1

×1n2

× . . .×1

nm< 1.

Aplicando log nos dois lados da desigualdade:log 1

n1× log 1

n2× . . .× log 1

nm< 0



se e somente se1n1

×1n2

× . . .×1

nm< 1.

Aplicando log nos dois lados da desigualdade:log 1

n1× log 1

n2× . . .× log 1

nm< 0

que é o mesmo que− log n1 ×− log n2 × . . .×− log nm < 0.


Substituindo os pesos das arestas:USD CAD AUD BRL ILS GBP EUR

USD 0 -0,05 -0,05 -0,39 -0,57 0,21 0,11CAD 0,05 0 0 -0,34 -0,53 0,26 0,15AUD 0,05 0,00 0 -0,33 -0,52 0,26 0,16BRL 0,39 0,35 0,34 0 -0,18 0,6 0,49ILS 0,59 0,54 0,52 0,19 0 0,80 0,7

GBP -0,21 -0,25 -0,26 -0,59 -0,78 0 -0,1EUR -0,1 -0,15 -0,16 -0,49 -0,68 0,11 0

USD = dólar dos EUACAD = dólar canadenseAUD = dólar australianoBRL = real BrasilILS = shekel (Israel)GBP = libra esterlina (Reino Unido)

EUR = euro


USD

BRL

CAD AUD

ILS

GBP

EUR

-0,05

-0,05

-0,39

0,7

0,21

0,11

0,05

0

-0,34 -0,53 0,

260,16

0,05

0,004

-0,33

-0,52

0,25

0,16

0,39

0,35

0,34

-0,18

0,60,49

0,59

0,520,

54

0,19

0,8

-0,21

-0,25

-0,26

-0,59

-0,78

-0,1-0,1

-0,15 -0,16

-0,49

-0,68

0,11

-0,57


USD

BRL

CAD AUD

ILS

GBP

EUR

-0,05

-0,05

-0,39

0,7

0,21

0,11

0,05

0

-0,34 -0,53 0,

260,16

0,05

0,004

-0,33

-0,52

0,25

0,16

0,39

0,35

0,34

-0,18

0,60,49

0,59

0,520,

54

0,19

0,8

-0,21

-0,25

-0,26

-0,59

-0,78

-0,1-0,1

-0,15 -0,16

-0,49

-0,68

0,11

-0,57

Lucro:se soma dos pesos do ciclo < 0


USD

BRL

CAD AUD

ILS

GBP

EUR

-0,05

-0,05

-0,39

0,7

0,21

0,11

0,05

0

-0,34 -0,53 0,

260,16

0,05

0,004

-0,33

-0,52

0,25

0,16

0,39

0,35

0,34

-0,18

0,60,49

0,59

0,520,

54

0,19

0,8

-0,21

-0,25

-0,26

-0,59

-0,78

-0,1-0,1

-0,15 -0,16

-0,49

-0,68

0,11

-0,57

Lucro:0,01


USD

BRL

CAD AUD

ILS

GBP

EUR

-0,05

-0,05

-0,39

0,7

0,21

0,11

0,05

0

-0,34 -0,53 0,

260,16

0,05

0,004

-0,33

-0,52

0,25

0,16

0,39

0,35

0,34

-0,18

0,60,49

0,59

0,520,

54

0,19

0,8

-0,21

-0,25

-0,26

-0,59

-0,78

-0,1-0,1

-0,15 -0,16

-0,49

-0,68

0,11

-0,57

Lucro:0,02


Resolução pelo algoritmo de Bellman-Ford:


Resolução pelo algoritmo de Bellman-Ford:• adicione um vértice v0 com uma aresta de peso 0 para

cada vértice;



cada vértice;

• a adição de v0 não pode criar novos ciclos;



cada vértice;

• a adição de v0 não pode criar novos ciclos;

• todos os ciclos do grafo são acessíveis a partir de v0;

Bibliografia Utilizada

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L. e STEIN, C.Introduction to Algorithms, 3a edição, MIT Press, 2009.

Documents

Caminho M nimo de Fonte nica em Grafos com Pesos Negativosprofessor.ufabc.edu.br/~leticia.bueno/classes/teoriagrafos/materiais… · vértices: algoritmo de Floyd-Warshall em tempoO(n3)