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

andronikus

[C++] Ajuda: Determinar Maior Caminho num Grafo (Resolvido)

3 mensagens neste tópico

Boas,

Tenho que fazer um trabalho que consiste basicamente na determinação do menor e do maio caminho num grafo. A determinação do menor caminho está a funcionar para qq tipo de grafos, contudo a determinação do maior caminho só funciona para grafos dirigidos.

Gostava de saber se alguem conhece algum algoritmo ou mesmo documentação (não existemt sobre isto na net) para que este algoritmo possa tb funcionar para todo o tipo de grafos,

Se me puderem ajudar fico agradecido :P

BOM NATAL ;)

cumps

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Documentação existe muita na net sobre isto. Na wikipedia por exemplo tem lá links muito úteis. ;)

Mas para saberes o caminho mínimo e maior osgrafos tem de ser dirigidos senão não faz sentido.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O maior caminho tem de pressupor uma de duas coisas: Ou que nunca passas duas vezes pelo mesmo vértice, ou que nunca passas duas vezes pela mesma corda.

Caso contrário, é óbvio que num grafo não dirigido é possível arranjar um caminho de comprimento infinito, basta andar constantemente entre dois pontos (para lá e para cá) e só depois te dirigires ao destino.

Se o que queres é saber o caminho mais longo passando uma única vez por cada edge, tens por exemplo os algoritmos para calcular eulerian paths. Está demonstrado que num grafo em que cada vértice possua um nível par é possível passar-se por todos lados somente uma vez e acabar no nó de origem (ou noutro qualquer). Se existirem 2 nós de nível ímpar é possível começar num deles e acabar no outro, percorrendo todos os edges somente uma vez.

Pesquisa por Eulerian Path / Eulerian Circuit.

Caso te estejam a pedir que para achar o maior caminho passando uma única vez por cada nó, acho que esse problema é NP-complete, procura por "Travelling salesman", acho que é o exemplo mais típico desse problema.

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