Achar o menor caminho entre cidades

[JDennis 0]

Por favor, alguém me ajuda nessa questão. Sou iniciante, comecei a pouco tempo estudar algoritmos e não estou conseguindo fazer usando matriz.
Se alguém poder me ajudar ficarei muito grato.

[Linguagem C]

 

A Figura abaixo representa as estradas conectando algumas cidades do País. O Governo Brasileiro contratou a sua empresa para desenvolver um algoritmo capaz de calcular as menores rotas, assim reduzindo os gastos com o escoamento da produção. Crie um algoritmo que receba as rotas abaixo e apresente em ordem crescente as melhores rotas para cada região.

Exemplo: Para a produção de Florianópolis chegar em Cametá existem dois caminhos possíveis:

1. Florianópolis – São Paulo – Fortaleza – Belém – Cametá
2. Florianópolis – São Paulo – Brasília – Belém – Cametá.

Apresente a total distância de ambas as rotas e qual é a mais viável. Após desenvolver o seu algoritmo, faça um teste de mesa para todas as possibilidades contidas no gráfico. Assim provando a eficácia do seu algoritmo.

 

 

 

[Beraldo 864]

Menor caminho está ligado ao problema do Caixieiro-Viajante. Leia sobre Teoria do Grafos e Busca em Largura, que encontrará a solução para o seu problema.

[JDennis 0]

Pois é Beraldo, não consigo entender grafos, pois já estudei só o básico de algoritmos na faculdade. Ainda não estudamos estrutura de dados.

[Motta 645]

http://www.ime.unicamp.br/sinape/19sinape/node/775

 

 

Uma nova abordagem.