Oi Blabos, Pelo o que você disse, no seu grafo as arestas não tem peso (ou todas tem o mesmo peso, e.g. 1) e o que você quer fazer é contar a distância entre 2 nós do grafo, então você pode utilizar um algoritmo mais simples como uma busca em largura para calcular a distância entre dois nós. Se sua representação do grafo for através de lista de adjacências, a BFS roda em tempo linear no tamanho do grafo - O(n + m) - enquanto a melhor implementação conhecida para o Dijkstra, com heap de fibonacci, fica em (n*logn + m) apesar de ser bem mais complexa de implementar.
[ ]'s 2013/9/20 Blabos de Blebe <[email protected]> > Opa, > > Nos capítulos anteriores... > > Eu procurei ajuda sobre como fazer uma conta e como executar essa conta de > forma assíncrona em relação à aplicação web. > > Os donos dos resultados dessa conta relacionam-se entre si de forma que eu > modelei esse relacionamento através de um grafo direcionado. > > Eu só precisava saber a quantos nós cada um deles está um do outro, eu nem > preciso do path em si. Um simples scalar( Graph::SP_Dijkstra( a, b ) ) - 1 > já me dá isso. > > É a partir dessa informação que eu *começo* o meu trabalho. > > Obrigado a todos que contribuíram com sugestões que eu já usei, e com > sugestões que ainda vou usar. > > []'s > > > 2013/9/19 Wagner Arbex <[email protected]> > >> Opa, tb fiquei curioso sobre a sua aplicação, Blabos. >> >> Fiz uma aplicação, na mão, em que precisava achar os componentes >> conexos e os ciclos e, depois, fiz uma outra versão usando as rotinas >> do módulo Graph-0.96 (http://search.cpan.org/perldoc?Graph), que vc tb >> citou. Ainda não gostei do que fiz e estou trabalhando em uma versão >> mais "sofisticada", tentando aplicar aprendizado de máquina, fazendo >> com que a rotina "adquira conhecimento" sobre os dados que recolhe ao >> longo de cada componente conexo que percorre. >> >> Posso estar enganado, mas não me lembro de ter visto ninguém falando >> sobre grafos a lista, por isso estou fiquei curioso qto à sua >> aplicação. >> >> Acho que existem outras questões que vc pode querer considerar no >> caminho entre dois vértices em um grafo. P. ex., só existe um caminho >> entre qq dois nós? Interessa saber se existe outro caminho? O que está >> sendo procurado é qq caminho ou um caminho específico, p. ex., o >> caminho mais curto ou caminho mais rápido? Existem "pesos" nas arestas >> entre os dois nós? Lembrando que uma árvore é um caso particular de >> grafo, o grafo é realmente um grafo ou uma árvore? >> >> Gostei da conversa e se eu achar que posso ajudar, vou tentar >> contribuir com alguns centavos. >> >> []s, W. >> >> 2013/9/19 Hernan Lopes <[email protected]>: >> > Blabos, o que vc quer fazer? >> > >> > 2013/9/19 Blabos de Blebe <[email protected]> >> >> >> >> E aí pessoal, >> >> >> >> Estou precisando calcular a distância entre nós em um grafo >> direcionado. >> >> >> >> É aquele algoritmo clássico que tem no Cormen ou qualquer livro >> decente do >> >> ramo. >> >> >> >> No cpan eu achei de interessante: >> >> >> >> https://metacpan.org/module/JHI/Graph-0.96/lib/Graph.pod >> >> https://metacpan.org/module/Paths::Graph >> >> https://metacpan.org/module/Boost::Graph >> >> https://metacpan.org/module/DBIx::Path >> >> >> >> Gostaria de ouvir a opinião de vcs a respeito, e se tiverem outras >> >> sugestões, sou todo ouvidos. >> >> >> >> []'s >> >> >> >> >> >> >> >> =begin disclaimer >> >> Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >> >> SaoPaulo-pm mailing list: [email protected] >> >> L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >> >> =end disclaimer >> >> >> > >> > >> > =begin disclaimer >> > Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >> > SaoPaulo-pm mailing list: [email protected] >> > L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >> > =end disclaimer >> > >> >> >> >> -- >> Wagner Arbex, DSc >> Bioinformática e modelagem matemática e computacional de biossistemas >> >> http://www.arbex.pro.br/ >> =begin disclaimer >> Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >> SaoPaulo-pm mailing list: [email protected] >> L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >> =end disclaimer >> > > > =begin disclaimer > Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ > SaoPaulo-pm mailing list: [email protected] > L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> > =end disclaimer > > -- Bruno C. Buss http://www.brunobuss.net
=begin disclaimer Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ SaoPaulo-pm mailing list: [email protected] L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> =end disclaimer
