2ª avaliação de Análise e Projeto de Algoritmos (2016.1)

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

Dado um grafo, seu programa deverá informar se é possível percorrer um caminho a partir de um ponto de partida determinado, passando por todos os vértices, sem repetir e voltar ao ponto de partida. Caso existam mais de um caminho possível, o programa deve exibir o menor.

Além do programa, você deve enviar um documento com a análise do algoritmo que você criou.

A entrada das informações do grafo se dará por um arquivo de texto no formato abaixo:

V
A
u v w
u v w
...

• V: número de vértices
• A: número de arestas
• u: vértice de origem
• v: vértice de destino
• w: peso

Os vértices sempre começam do 0. Exemplo:

4
6
0 1 10
1 2 10
2 3 10
3 0 10
0 2 1
1 3 1