Algoritmos Redes

Departamento de Economia, Gestão e Engenharia Industrial
Universidade de Aveiro
Disciplina: INVESTIGAÇÃO OPERACIONAL I

ALGORITMOS PARA A RESOLUÇÃO DE
PROBLEMAS EM REDES

Problema da ÁRVORE MÍNIMA DE SUPORTE

Algoritmo de Prim
1. Seleccionar um nó arbitrariamente e ligá-lo ao nó mais próximo.
2. Identificar o nó ainda isolado que esteja mais próximo de um nó já ligado e ligar estes dois nós.
Repetir 2. até que todos os nós estejam ligados entre si.
Aplicação do algoritmo de Prim ao problema do parque natural
(1)

5

2

5

O

1

(3)

2

5

O

5

2

B
1

C

W

D

4

7
3

4

4

B

1

E

1

4

E

(4)

2

C

7

4

1

E

7

A

5

2

5

O

1

C

W

D

4

B

7
3

4

W

D

4
3

7

A

5

2

1

4

C

7

A
5

O

7
3

2

W

D

4

B

4

(2)

7

A

2

4

1

E

1

Problema da ÁRVORE MÍNIMA DE SUPORTE
Aplicação do algoritmo de Prim ao problema do parque natural (cont.)
(5)

5

2

5

O

B
1

C

2

7

A
5

O

7

5

2

W

D

4
3

4

(6)

7

A

2

B

7
3

1

4

4

E

W

D

4

1

1

4

C

Fim

E

Problema da ÁRVORE MÍNIMA DE SUPORTE

Algoritmo de Prim em quadro
1. Seleccionar um nó arbitrariamente e fazer um traço sobre a linha e a coluna do nó seleccionado.
2. Seleccionar, de entre os elementos com um só traço, aquele que tiver o menor valor, marcando com um círculo. Fazer um traço sobre a linha e a coluna do nó acabado de ligar.
Repetir 2. até que todas as linhas e todas as colunas estejam traçadas.
Aplicação do algoritmo de Prim em quadro ao problema do parque natural
(1)

(2)

O

O

(O,A)

A

2

B

5

C

4

-

1

D

-

7

4

-

E

-

-

3

4

1

W

-

-

-

-

5

7

O

A

B

C

D

E

2

W

(3)
O

(B,A)

A

2

B

5

2

C

4

-

1

D

-

7

4

-

E

-

-

3

4

1

W

-

-

-

-

5

7

O

A

B

C

D

E

W

(B,C)

A

2

B

5

C

4

-

D

-

7

4

-

E

-

-

3

4

1

W

-

-

-

-

5

7

O

A

B

C

D

E

2
1

W

2

Problema da ÁRVORE MÍNIMA DE SUPORTE
Aplicação do algoritmo de Prim em quadro ao problema do parque natural (cont.)
(4)

(5)

O

O

(B,E)

A

2

B

5

C

4

-

1

D

-

7