2ª avaliação da disciplina EXA813 – Análise e Projetos de Algoritmos

2ª avaliação da disciplina EXA813 – Análise e Projetos de Algoritmos
Valor: 10,0 na 2ª unidade.
Prazo: 15/04/2016, 23:59 (via e-mail).
Em dupla.

Escreva um programa (em qualquer linguagem) que leia um arquivo de configuração de grafo (modelo abaixo) e trace o percurso de menor caminho entre dois pontos, passando por outros dois pontos adicionais.

O programa deverá ler o arquivo de configuração, armazenar o grafo em memória e em seguida solicitar os dados do trajeto ao usuário. Os dados solicitados serão: ponto de partida, destino e dois pontos intermediários.

Ex.: suponha que o grafo contenha pontos conhecidos de Feira de Santana. O usuário poderia indicar como origem “UEFS”, destino “Rodoviária”, passando por “Hiper G Barbosa” e “Shopping”. Ao traçar o menor caminho, a melhor opção nesse caso seria “UEFS” -> “Shopping” -> “Hiper G Barbosa” -> “Rodoviária” (perceba que não é necessário passar nos pontos intermediários na ordem que foram especificados, seu programa deverá verificar qual o melhor intinerário).

O arquivo de configuração conterá o número de vértices, o nome de cada vértice, o número de arestas e a configuração de cada aresta na forma “origem,destino,peso” (o peso indica a distância em Km). Veja o exemplo:

6
UEFS
Shopping
Hiper G Barbosa
Quatro Estações
Rodoviária
Empório da Cerveja
5
UEFS,Shopping,4
UEFS,Hiper G Barbosa,7
Quatro Estações,UEFS,0.6
Rodoviária,Empório da Cerveja,4
Empório da Cerveja,Shopping,4