Adstrwrt

INSTITUTO MILITAR DE ENGENHARIA
PÓS-GRADUAÇÃO EM ENGENHARIA DE TRANSPORTES

Algoritmos para Resolução de
Problemas em Redes

Prof.ª Vânia Barcellos G. Campos

Índice

pag

1- Definição e Conceitos Básicos sobre Grafos

1

1.1 Conceitos Básicos

1

1.2 Características Estruturais

2

2- Conceituação de Redes

2

3- Minimização de Redes

4

3.1 Algoritmo de Kruskal

4

3.2 Algoritmo de Prim

6

4- Algoritmos de Caminho Mínimo

6

4.1 Algoritmo de Dijkstra

7

4.2 Algoritmo de Ford, Bellman e Moore

9

4.3 Caminho mais Confiável

11

4.4 Algoritmo de Floyd

12

4.5 Algoritmo de Dantzig

13

4.6Algoritmo de K-caminhos mínimos

13

4.7Desempenho dos Algoritmos

14

5- Algoritmos de Fluxo Máximo

15

5.1 Conceitos Básicos

15

5.2 Algoritmo de Aumento de Fluxo

17

5.3 Algoritmo de Ford /Fulkerson

19

5.4 Algoritmo de Dinic

20

5.5 Algoritmo DMKM

21

5.6 Modificações na Estrutura da Rede

22

5.7 Análise dos Algoritmos

23

6- Algoritmos de Custo Mínimo

24

6.1 Algoritmo Busacker e Gowen

24

6.2 Análise dos Algoritmos de custo Mínimo

26

7 - Roteirização

27

Bibliografia

28

Lista de Exercícios

29

1

1- Definição e Conceitos Básicos sobre Grafos
Um grafo G = (X,A) é uma estrutura composta por um conjunto X de elementos chamados vértices ou nós e um conjunto A de pares de vértices, chamados arcos ou arestas. A representação gráfica de um grafo é feita por pontos (vértices) e linhas (arestas) unindo estes pontos.
Quanto as características de seus arcos, um grafo pode ser :
a) Orientado e não orientado
São orientados quando seus arcos possuem uma orientação definida , ou seja , um nó do arco é definido como origem do mesmo e o outro como destino. E, não orientado, quando não existe esta noção de direção.
b) Valorado e não valorado
Um grafo é valorado, quando existem valores atribuídos a cada um dos seus arcos.
Exemplo