Dijkstra (Menor caminho)

[Lucas NN]

Olá,

Eu implementei em C o algoritmo de Dijkstra.

O meu algoritmo recebe como entrada uma cidade e guarda em memória o menor caminho dela até cada uma das outras cidades do mapa.

Isso está feito e funcionando perfeito.

Porém preciso ter como saída o trajeto para viajar por todas as cidades do mapa utilizando o menor caminho retornando ao final à origem.

Meu algoritmo só consegue descobrir o melhor caminho entre duas cidades (origem e destino), porém não sei como implementar o algortimo para que apartir da origem viaje por todo o mapa e retorne à origem.

O mapa: ftp://ftp-acd.puc-campinas.edu.br/pub/pro...os%20Unidos.jpg

As cidades que podem ser utilizadas na entrada (origem): Miami, Nova York, Dallas, Los Angeles, Atlanta ou Chicago (apenas essas cidades podem ser utilizadas como cidade de origem)

Gostaria de dicas de como terminar o algoritmo.

Enunciado do professor:

DESCRIÇÃO

Uma agência de viagens deseja ajudar seus clientes a conhecer os Estados Unidos e pede

sua ajuda.

Os clientes irão de avião até Miami, Nova York, Dallas, Los Angeles, Atlanta ou Chicago. A

partir daí, alugarão um carro para conhecer uma lista grande de cidades. No final, devem

voltar à cidade de partida, devolver o carro alugado e retornar ao Brasil.

O problema dos clientes é que a lista de cidades que querem visitar é muito grande, e

existem muitas estradas conectando as cidades. Os clientes querem um percurso que

minimize a distância que terão que dirigir, mas não sabem como encontrá-lo. Felizmente,

eles já têm a lista de cidades desejadas, as estradas que as conectam e as respectivas

distâncias (arquivo Estados Unidos.pdf).

PROJETO BÁSICO [5 PONTOS]Implemente um programa que tenha como entrada a cidade onde o cliente irá desembarcar,

e como saída o percurso visitando todas as cidades e retornando à cidade inicial. O

programa deverá mostrar claramente todos os trechos percorridos, a distância de cada

trecho, e a distância total a ser percorrida.