Algoritmos em Grafos

Algoritmos em GrafosAlgoritmos em Grafos

Celso C. RibeiroCaroline T. Rocha

22Algoritmos em Algoritmos em GrafosGrafos

PARTE 2: CAMINHOS MAIS CURTOS


Caminhos mais CurtosCaminhos mais Curtos

Dados: grafo G=(V,A) orientado e distância cij associada ao arco (i,j) A.

Problema: Obter o caminho mais curto entre dois nós s e t.

O comprimento de um caminho é igual à soma dos comprimentos (distâncias) dos arcos que formam o caminho.A “distância” ou “comprimento” de um arco pode ter diversas interpretações dependendo da aplicação: custos, distâncias, consumo de combustível, etc.

Exemplo 1: Dado um mapa rodoviário, determinar a rota mais curta de uma cidade a outra.(rota mais rápida, rota com menor consumo de combustível, ...)



Exemplo 2: Construção de uma estrada entre duas cidades A e K. O grafo abaixo representa os diversos trechos possíveis e o custo de construção de cada um. Determinar o trajeto ótimo cujo custo de construção seja mínimo (corresponde a achar o caminho mais curto de A a K em relação a estes custos).

A

B

C

D

F

E

G J

I

H

K

8

7

5

6 4

2 4

5

4

4

2

244

5

2 4 4

Solução: A – D – G – I – Kcusto = 7 + 2 + 2 + 5 = 16



Condição de existência: Caminho de i a j contendo um circuito w:

kj

i

w

Comprimento do caminho =comprimento (i k) +comprimento (w) +comprimento (k j)

Qual é o comprimento do caminho mais curto de i a j se o comprimento do circuito w é negativo?



Condição de existência: não há circuitos de comprimento negativo.

A solução ótima (caminho mais curto) sempre será um caminho elementar (sem circuito).



Caminho mais curto:- De um nó a outro- De um nó a todos os demais- Entre todos os pares de nós de um grafo


Caminho mais curto do nó 1 a cada nó do grafo G=(V,A)

Hipótese: todas as distâncias cij são positivas:

cij ≥ 0, (i,j) A

Algoritmo de Moore-Dijkstra (1957-1959)*(i) = comprimento do caminho mais curto do nó 1 ao nó iEm especial, *(1)=0 (distâncias positivas).

Algoritmo com n-1 iteraçõesNo início de cada iteração, o conjunto V de nós está particionado em dois subconjuntos S e S, com o nó 1 em S.

VSS

SS



Cada nó i V possui um rótulo (i ), que verifica a seguinte propriedade:


)(*)( Se

)(*)( Se

iiSi

iiSi

ki

ΓkSk

ckii

)(min)(

dá o valor do caminho mais curto de 1 a i sob a restrição de que todos os nós utilizados (exceto o próprio i ) pertençam a S.

, ),( Sii

a

1 b

c

i

)(a

)(b

)(c

)(icai

cbi

cci

SS



Teorema: Seja o nó tal que .Então , isto é, o comprimento do caminho mais curto do nó 1 ao nó j é igual a .

Sj )( min)( ijSi

)( )(* jj

Demonstração:

Por construção, certamente existe um caminho de 1 até j com comprimento (j).

Suponhamos que exista outro caminho de 1 a j de comprimento menor do que (j).

Dividamos este caminho em duas partes:

- P1 é a parte inicial, do nó 1 ao nó L, onde L é o primeiro nó de encontrado

- P2 é a parte final, do nó L ao nó j

)( j

S



comprimento de P1 ≥ (L) ≥ (j)

comprimento de P2 ≥ 0

Logo, o comprimento de P1 + P2 ≥ (j).



Algoritmo de Moore-Dijkstra

O algoritmo constrói progressivamente o conjunto dos nós mais próximos de 1. Construção de uma arborescência com raiz em 1 que define os caminhos mais curtos do nó 1 a cada nó do grafo.

Inicializar S {2,3,...,n}, S {1}, (1) 0, (j) c1j se j1

+

+ caso contrárioEnquanto S faça Selecionar jS tal que (j)= miniS{(i)} S S – {j} Para iS e ij

+ faça (i) min{(i), (j)+cji}fim_enquanto



Exemplo:

1

2

3

4

5

61

2

35

7

7

5

1 2

4

ITERAÇÃO 1

*(1) = 0

*(3) = 1

1

2

3

4

5

61

2

35

7

7

5

1 2

4

S = {1}S = {2,3,4,5,6}(1) = 0(2) = 7(3) = 1(4) = (5) = (6) = +

(2) = min{7, (5) = min{, (6) = min{,

j = 3S = {2,4,5,6}

1+5} = 6

1+2} = 31+7} = 8



ITERAÇÃO 2

(2) = min{6, (4) = min{,

j = 5S = {2,4,6}

3+2} = 5

3+5} = 8

*(1) = 0

*(3) = 1

1

2

3

4

5

61

2

35

7

7

5

1 2

4 *(5) = 3

ITERAÇÃO 3

(4) = min{8, (6) = min{,

j = 2S = {4,6}

5+4} = 8

5+1} = 6

*(1) = 0

*(3) = 1

1

2

3

4

5

61

2

35

7

7

5

1 2

4 *(5) = 3*(2) = 5



ITERAÇÃO 4

(4) = 8

j = 6S = {4}

ITERAÇÃO 5

j = 4S = { }

*(1) = 0

*(3) = 1

1

2

3

4

5

61

2

35

7

7

5

1 2

4 *(5) = 3*(2) = 5

*(6) = 6

*(1) = 0

*(3) = 1

1

2

3

4

5

61

2

35

7

7

5

1 2

4 *(5) = 3*(2) = 5

*(6) = 6

*(4) = 8



1

2

3

5

42

3

25

4

3

1 2

6

7

3

1

4

3

1 2 3 4 5 6

1

2

3

4

5

6

7

nóIteração

Início

0

4

2

0

4

2

5

4

7

7

0

4

2

5

4

0

4

2

5

4

7

7

0

4

2

5

4

7

7

0

4

2

5

4

7

7

0

4

2

5

4

7

7



Número de operações (tempo): ~ n2

n-1 iterações, cada iteração busca o mínimo em uma lista com até n-1 elementos (vetor )

Caminho mais curto do nó 1:

ao nó j

a todos os nós

Mesma complexidade, mas critérios de parada diferentes.

Distâncias negativas:

1

3

210

- 8

3

Caminho mais curto de 1 a 3?

Resultado do algoritmo?

2

3

Por que?


Inicializar S {2,3,...,n}, S {1}, (1) 0, (j) c1j se j1

+

+ caso contrárioEnquanto S faça Selecionar jS tal que (j)= miniS{(i)} S S – {j} Para ij

+ faça Calcular * (j)+ cji

Se * < (i) então S S {i} (i) * fim-se fim-parafim-enquanto


Extensão do algoritmo de Moore-Dijkstra para o caso com distâncias negativas (mas sem ciclos negativos)



1

2

3

5

42

3

-2-3

4

3

1 2

6

7

3

1

4

3

1 2 3 4 5 6 7 8

1

2

3

4

5

6

7

nóIteração

Início

0

4

2

S = 2 3 4 5 6 7

0

4

2

5

4

0

4

1

5

4

7

7

0

4

2

5

4

7

7

0

4

1

4

2

6

6

0

4

1

4

2

5

5

0

4

1

4

2

5

5

0

4

1

4

3

7

7

0

4

1

4

3

6

6

XX 3X

3

X

5

X 5X

5

X X

7



Caminho mais curto:- De um nó a outro- De um nó a todos os demais- Entre todos os pares de nós de um grafo



Dados: Grafo G=(V, A) orientado, |V | = n.Não há circuitos negativos.c = {cij}, j = 1,...,n, i = 1,...,n

cij ≥ 0

cii = 0

cij = +, (i, j ) A

Ak(i, j ) = valor do caminho mais curto de i a j podendo usar apenas nós numerados de 1 a k como nós intermediários.

Caminho mais curto entre todos os pares de nós de um grafo



A0(i, j ) = cij : caminho mais curto de i a j usando no máximo o nó “0” (que não existe) como nó intermediário (caminho mais curto de i a j sem nós intermediários)

Ak(i, j ) : pode usar o nó k ou não.

Ak+1(i, j ) : pode usar o nó k+1 ou não.

A0 A1

A1 A2

...

An-1 An

An(i, j ) = valor do caminho mais curto de i a j podendo usar qualquer nó de 1 a n como nó intermediário.



Se Ak+1(i, j ) não usa o nó k+1 como intermediário, então: Ak+1(i, j ) = Ak(i, j )

Ak+1(i, j ) = min { Ak(i, j ), Ak(i, k+1) + Ak(k+1, j ) }Ak+1(i, j ) = min { Ak(i, j ), Ak(i, k+1) + Ak(k+1, j ) }

Se Ak+1(i, j ) usa o nó k+1 como intermediário, então: Ak+1(i, j ) = Ak(i, k+1) + Ak(k+1, j )



Algoritmo de Floyd:

Para i = 1,...,n faça Para j = 1,...,n faça

A0(i,j) cij

fim-parafim-paraPara k = 1,...,n faça Para i = 1,...,n faça Para j = 1,...,n faça Ak(i,j) min{Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j)} fim-para fim-parafim-para


073

206

1140A1 =


Exemplo:

1 2

3

3

6

4

11 2 0+∞3

206

1140C =

0+∞3

206

1140A0 =

073

206

640A2 =

073

205

640A3 =



Algoritmo de Dijkstra: número de operações (tempo) ~ n2

n-1 iterações, cada iteração busca o mínimo em uma lista com até n-1 elementos (vetor )

Algoritmo de Floyd: número de operações (tempo) ~ n3

Três comandos for de 1 até n um dentro do outro

Ou seja, o problema de calcular os caminhos mais curtos entre todos os pares de nós pode ser resolvido com a mesma eficiência aplicando-se n vezes o algoritmo de Dijkstra, uma vez a partir de cada nó inicial.

Documents

Algoritmos em Grafos