C / C++ Menor caminho em grafo ponderado [Linguagem C]

[GuiEssence]

Fala galera, beleza?

Seguinte, tenho um problema para resolver e não estou conseguindo engrenar o pensamento:

Eu tenho que fazer um grafo, baseando-se em um mapa real (no meu caso, Serra Gaúcha) que conta com 12 cidades principais, cada cidade com vários arcos e entre esses arcos outras cidades.



Como posso criar uma estrutura que abrigue todos esses pontos e arcos?

Meu objetivo é fazer um programa em que o usuario escolha uma cidade inicial e mostra o menor caminho passando por todas as cidades.

Valeu galera!

[cristianoborgescardoso]

Tenho um algorítimo que resolve esse problema. Vai precisar ainda?

Fala galera, beleza?

Seguinte, tenho um problema para resolver e não estou conseguindo engrenar o pensamento:

Eu tenho que fazer um grafo, baseando-se em um mapa real (no meu caso, Serra Gaúcha) que conta com 12 cidades principais, cada cidade com vários arcos e entre esses arcos outras cidades.



Como posso criar uma estrutura que abrigue todos esses pontos e arcos?

Meu objetivo é fazer um programa em que o usuario escolha uma cidade inicial e mostra o menor caminho passando por todas as cidades.

Valeu galera!

[cristianoborgescardoso]

Cara , eu tenho um algorítimo pronto em java.

Eu fiz pra outor mapa, de outra cidade.

Vc vai ter q adicionar outras cidades e adicionar caminhos entre elas.

Os erros não estão devidamente tratados. De modo que, se você inserir as cidades, más não inserir caminhos suficientes para o agente percorrer todas as cidades e voltar para a cidades de origem, o algorítimo não funcionará.

Aconselho inserir uma cidade e os caminhos necessários para o agente "vir"para a cidade por um caminho e "voltar" por outro caminho.

Espero que ajude.

Abs,

Cristiano.

[flaviotps]

Bom, grafos normalmente são representados como matrizes ou listas simples/duplamente encadeadas...


geralmente assim ... vamos supor um grafo bem simples (bidirecional)

......0
........\
.........1
......./...\
......2.....3
..............\
..............4

Esse grafo pode ser representado como uma lista simples dessa forma...

typedef struct lista
{
int vertice;
int peso; //opcional usado para calcular o melhor caminho ou caminho de menor custo
struct lista * prox;
}lst;

a lista deve serguir um modelo,vou fazer um modelo mais facil para esse exemplo.

lst[vertice] -> lst[vertice] (o vertice qualquer aponta para outro)

ou seja

lst[0]->lst[1]
lst[1]->lst[0]
lst[1]->lst[2]
lst[1]->lst[3]
lst[2]->lst[1]
lst[3]->lst[4]
lst[3]->lst[1]
lst[4]->lst[3]


ou usando matrizes

0 1 2 3 4
0 0 1 0 0 0
1 1 0 1 1 0
2 0 1 0 0 0
3 0 1 0 0 1
4 0 0 0 1 0



Para calcular as melhores rotas aconselho pesquisar e usar o algoritmo de dijkstra .

Algoritmo que verifica se ha rota entre 2 vertices :

int Conexao(lst **grafo, int *vet, int pos, int destino)
{
if(vet[pos-1]==destino)
return 1;
else
{
int indice=vet[pos-1];
lst*p=grafo[indice];
while(p!=NULL)
{
if(existe(vet, pos, p->vertice)==0)
{
vet[pos]=p->vertice;
if(Conexao(grafo, vet, pos+1, destino))
return 1;
}
p=p->prox;
}

}
return 0;
}

na Main,deve ser usado assim :

vet[0]=origem;
int caminho=Conexao(grafo,vet,origem,destino);

Espero ter ajudado,caso precise tenho alguns codigos que fiz usando esse algoritmo.