Algoritmos em grafos

Departamento de Ciência da Computação-UFMG
ALGORITMOS E ESTRUTURAS DE DADOS III
Nome: Pedro Magalhães Fortini
TRABALHO PRÁTICO 1

1. Introdução

O objetivo principal do trabalho prático proposto é a implementação e uso de algoritmos para a estrutura de dados grafo, além do exercício da linguagem de programação C. Para tal, nos foi apresentado o problema de alocação da filial de uma empresa distribuidora de produtos chamada Atlanticon. A Atlanticon decidiu instalar uma nova filial em dada região e necessita saber onde deve ser instalada sua filial, dessa forma, ela conta com a malha viária da região o que permite saber a distância entre duas cidades quaisquer que sejam conectadas por algum trilho. De posse da malha viária, o objetivo é determinar qual é a melhor cidade para a instalação da filial em cada um de três cenários possíveis, são eles:

- Cenário 1: No primeiro cenário a cidade deve ser escolhida de modo a minimizar os custos de entrega da Atlanticon, em especial o gasto em combustível pelos trens. Considerando que cada cidade emite a mesma quantidade de pedidos em um mesmo intervalo de tempo.

- Cenário 2: Nesse cenário deve ser levado em conta também o número de pedidos feito por cada cidade. Assim, além da malha de distâncias entre as cidades, também será fornecida a média de pedidos de cada cidade. Considerando que a proporção desses pedidos entre as cidades vai se manter a mesma, devemos agora decidir a
Localização da filial levando em conta o volume de pedidos de cada cidade além de minimizar o gasto de combustível nas entregas.

- Cenário 3: A Atlanticon decidiu lançar um novo serviço que consiste em uma taxa adicional paga no momento da compra de modo a garantir que produto será entregue rigorosamente dentro de um prazo de X horas. A empresa, portanto, gostaria de saber em qual cidade deveria ser instalada a filial para garantir o menor valor de X, considerando que todos os trens viajam a velocidade constante.

Além de determinar