Arquivo Discussoes de Programacao e Tecnologia Com certeza todos os colegas mais avançados aqui do fórum já trabalharam com grafos, pelo menos na faculdade. Gostaria de saber, se vocês poderiam ajudar um “quase” calouro na faculdade de SI. Pois bem, estou fazendo um trabalho sobre grafos e gostaria de saber se vocês conhecem algum algoritmo que calcula quantos caminhos o grafo pode ter de uma determinda origem até um determinado destino!
Se puderem me ajudar! Muito obrigado mesmo!
Leia http://en.wikipedia.org/wiki/Glossary_of_graph_theory e diga exatamente o que você entende por um “caminho”.
Por exempo, temos o grafo:
B
/ \
A D - E
\ /
C
Gostaria de saber os caminhos de A até E.
No caso, os caminhos seriam ABDE, ACDE, logo a resposta seria 2.
Então, segundo a referência, você quer contar quantos “trails” (“cadeias simples”) são possíveis do vértice A até o vértice E.
Amigo,
eu pensei um pouco e não consegui ver nenhum outro algoritmo que não seja você, partindo do vértice inicial, testar todas as possibilidades de caminho, e cada vez que um caminho chegar ao vertice final, você soma 1, e começa de novo. Vc só precisa bolar uma estratégia de ordem dos caminhos para não repetir uma tentativa de mesmo caminho.
Esse algoritmo vai ficar bem lerdo, mas até onde eu conseguir ver é a única alternativa. Se vc achar um só caminho seria bico, mas do jeito que vc quer, não vejo outra alternativa.
[]s