ATPS - ESTRUTURA DE DADOS MUDAR

Prof. Ricardo Barbosa

ATPS – ESTRUTURA DE DADOS

ALTERAÇÃO PASSO 3 DA ETAPA 4

Passo 3 (Equipe)

Introdução

A empresa VOEBEM esta expandindo seu negócio e contratou uma empresa terceirizada de

taxi para auxiliar seus passageiros a se deslocarem entre as cidades da RMC (Região

Metropolitana de Campinas). A empresa VOEBEM está desenvolvendo um sistema GPS próprio

e irá fornecê-lo para a empresa terceirizada de taxi.

1. Fazer um programa em Linguagem C que implemente um levantamento de rotas entre

uma Cidade A e uma Cidade B por meio de um Grafo, utilizando Matriz de Adjacência.

Considerar o total de 19 cidades da RMC (ver Figura 1). O programa deverá permitir

ao operador:

a. Informar a cidade de origem e a cidade de destino

b. Indicar o menor caminho entre as cidades informadas pelo usuário (se possível

indicar os três menores caminhos)

c. Informar trajeto para visitar todas as cidades a partir de uma cidade de origem

que será informada pelo usuário

A Figura 1 representa o mapa da Região Metropolitana de Campinas. As linhas

(arestas) em vermelho representam o caminho e os números em amarelo

representam as distâncias entre as cidades.

2. Implementar a função montarGrafo() que permita registrar, as dezenove cidades e

determinar se há ligação entre elas e qual a distância entre as cidades.

SUGESTÃO: Em um arquivo texto fazer o mapeamento entre as cidades e fazer a

função ler o arquivo e montar a matriz de adjacências.

3. Implementar a função menorCaminhoEntreCidades() que permita determinar qual o

melhor caminho entre uma cidade A e uma cidade B, considerando a distância e a

ligação entre as cidades.

4. Implementar a função visitarTodasCidades() que permita exibir uma rota de visita para

todas as cidades. FiFigura 1 – Mapa Região Metropolitana de Campinas