Algoritmo para Resolução de Grafos

Tr´ balho Pr´ tico 1 a a
Grafos
Thiago Lucas dos Santos Sandi
1

Departamento de Ciˆ ncia da Computacao - Universidade Federal de Minas Gerais(UFMG) e ¸˜ [e-mail] Resumo. Este relat´ rio descreve uma solucao proposta de um algoritmo que reo
¸˜
solve 3 cen´ rios onde vocˆ prestar´ consultoria para uma grande distribuidora a e a de produtos, a Atlanticon.

1. Indroducao
¸˜
A empresa Atlanticon pretende instalar uma nova filial de distribuicao para servir uma
¸˜
regi˜ o e deve ser escolhida em qual cidade ser´ instalada de acordo com cada cen´ rio a a a citado abaixo:
1.1. Cen´ rio 1: a No Cen´ rio 1 deve se escolher a cidade onde a filial ser´ instalada de modo a minimizar os a a custos de entrega e os gastos de combust´vel , onde cada cidade emite a mesma quantidade ı de pedidos em um mesmo intervalo de tempo.
1.2. Cen´ rio 2: a No Cen´ rio 2 foi observado que algumas cidades fazem mais pedidos que as outras. Asa sim deve se escolher a cidade onde a filial ser´ instalada levando em conta o n´ mero de a u pedidos de cada cidade de modo a minimizar os gastos no combust´vel. ı 1.3. Cen´ rio 3: a ´
No Cen´ rio 3 foi lancado um novo servico que consiste em uma taxa adicional que e paga a ¸
¸
no momento da compra que garante que o produto ser´ entregue dentro de um prazo de a X horas. Assim deve se escolher a cidade onde a filial ser´ instalada garantindo o menor a valor de X.

2. Modelagem e Solucao Proposta
¸˜
Neste projeto foi implementado como estrutura principal o TipoGrafo para criar um
Grafo que contˆ m um tipo matriz, um inteiro para o n´ mero de V´ rtices, e um inteiro e u e para o n´ mero de Arestas. A matriz do TipoGrafo foi alocada dinamicamente usando a u funcao malloc, e desalocadas usando a funcao free(). A modelagem foi feita em um grafo
¸˜
¸˜ ponderado n˜ o-direcionado. a Na pr´ xima p´ gina temos um exemplo de um grafo ponderado n˜ o direcionado. o a a Veja figura