• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

lesiano

Custo mínimo num grafo

14 mensagens neste tópico

Boas;

Tenho um grafo que é uma lista ligada de listas ligadas. Sabem onde posso arranjar um algoritmo pré-feito que me calcule o custo mínimo?

Obg.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não deves ter reparado que não explicaste o que querias. Custo mínimo de quê? Shortest Paths, Minimum Spanning Tree, Minimum Cut, Min-Cost Maximum Flow,....

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Desculpem, não me expressei bem.

Eu tenho dois nós num grafo, no caso duas cidades. E queria calcular o custo mínimo entre tais cidades.

Cada cidade tem ligações ( a lista ligada apontada em cada nó da lista ligada de todas as cidades ), em que têm associado um custo.

Possivelmente será o "Shortest Paths".

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Thx!!!

Mal tenha tempo vejo com pormenor, mas dá para lista de listas?

OBg. :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Claro que dá!

Já agora, se o número de nós não for muito grande, podes usar um algoritmo muito mais simples, que é o Floyd-Warshall. Ain't it, Mr. mogers? :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

10 000 cidades no mínimo, suponho q cada uma com 500 ligações.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vou então converter para código adaptado à minha lista.

Se tiver dúvidas meto neste tópico, ok?

Obg.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ora bem, comecei então a fazer o algoritmo de Dijkstra. Ou pelo menos a tentar.

Antes de mais, cada cidade deve ter um campo "visitado", um campo "distância" e um campo "pai" ou mais vale usar arrays para fazer isso, meter lá os valores e ir comparando a posição na lista com a posição no array?

Se alguém puder expor uma explicação mais detalhada do algoritmo agradecia. Eu fiquei com algumas dúvidas, vou colocar o que percebi:

i) Um ciclo para inicializar algumas coisas;

Para todos os vértices do grafo:

vertice->distância = +infinito; //Distância do vértice i à origem;

vertice->visitado = 0;          //Já foi visitado? 0/1;

vertice->pai = NULL;            //Qual o seu pai?

ii) Inicializar a distancia da origem à origem ( 0 );

origem->distância = 0;

iii)

6 enquanto(nos_visitados < tamanho_do_grafo)

    # encontrar o vértice não visitado com a distância mínima à origem; chamemos-lhe i

7  assert (distancia(i) != infinito, "Grafo não é conexo")

8  visitado(i) = Verdadeiro # marcamos o vértice i como visitado

    # actualizamos as distância para todos os vizinhos de i

9  Para todos os vizinhos j do vértice i

10      se distancia(i) + peso(i,j) < distancia(j) então

11          distancia(j) = distancia(i) + peso(i,j)

12          pai(j) = i

O ponto iii) ñ percebi. Alguém me pode explicar sff? Obg.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Usar os arrays ou campos vai dar ao mesmo, mas penso que é melhor usar como campos dum struct.

i) e ii) Sim, está bem.

iii) eu não percebi o que é que não percebeste :x

Tipo

# encontrar o vértice não visitado com a distância mínima à origem; chamemos-lhe i

para todos os vértices encontrar o vertice i dentro de todos os vértices com vertice->visitado = 0 que tem a menor vertice->distancia

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já percebi e já implementei sem erros, thx.

Já agr, existe algum algoritmo que devolva todos os caminhos entre dois vértices num grafo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora