2\u00aa avalia\u00e7\u00e3o da disciplina EXA813 \u2013 An\u00e1lise e Projetos de Algoritmos
\nValor: 10,0 na 2\u00aa unidade.
\nPrazo: 15\/04\/2016, 23:59 (via e-mail).
\nEm dupla.<\/p>\n
Escreva um programa (em qualquer linguagem) que leia um arquivo de configura\u00e7\u00e3o de grafo (modelo abaixo) e trace o percurso de menor caminho entre dois pontos, passando por outros dois pontos adicionais.<\/p>\n
O programa dever\u00e1 ler o arquivo de configura\u00e7\u00e3o, armazenar o grafo em mem\u00f3ria e em seguida solicitar os dados do trajeto ao usu\u00e1rio. Os dados solicitados ser\u00e3o: ponto de partida, destino e dois pontos intermedi\u00e1rios.<\/p>\n
Ex.: suponha que o grafo contenha pontos conhecidos de Feira de Santana. O usu\u00e1rio poderia indicar como origem “UEFS”, destino “Rodovi\u00e1ria”, passando por “Hiper G Barbosa” e “Shopping”. Ao tra\u00e7ar o menor caminho, a melhor op\u00e7\u00e3o nesse caso seria “UEFS” -> “Shopping” -> “Hiper G Barbosa” -> “Rodovi\u00e1ria” (perceba que n\u00e3o \u00e9 necess\u00e1rio passar nos pontos intermedi\u00e1rios na ordem que foram especificados, seu programa dever\u00e1 verificar qual o melhor intiner\u00e1rio).<\/p>\n
O arquivo de configura\u00e7\u00e3o conter\u00e1 o n\u00famero de v\u00e9rtices, o nome de cada v\u00e9rtice, o n\u00famero de arestas e a configura\u00e7\u00e3o de cada aresta na forma “origem,destino,peso” (o peso indica a dist\u00e2ncia em Km). Veja o exemplo:<\/p>\n
6\r\nUEFS\r\nShopping\r\nHiper G Barbosa\r\nQuatro Esta\u00e7\u00f5es\r\nRodovi\u00e1ria\r\nEmp\u00f3rio da Cerveja\r\n5\r\nUEFS,Shopping,4\r\nUEFS,Hiper G Barbosa,7\r\nQuatro Esta\u00e7\u00f5es,UEFS,0.6\r\nRodovi\u00e1ria,Emp\u00f3rio da Cerveja,4\r\nEmp\u00f3rio da Cerveja,Shopping,4<\/pre>\n","protected":false},"excerpt":{"rendered":"2\u00aa avalia\u00e7\u00e3o da disciplina EXA813 \u2013 An\u00e1lise e Projetos de Algoritmos Valor: 10,0 na 2\u00aa unidade. Prazo: 15\/04\/2016, 23:59 (via e-mail). Em dupla. Escreva um programa (em qualquer linguagem) que leia um arquivo de configura\u00e7\u00e3o de grafo (modelo abaixo) e …<\/p>\n