Re: [obm-l] Grafos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Grafos

on 05.04.03 19:16, Jhonata Emerick at jhonobm@yahoo.com.br wrote:

Olá pessoal da lista, quem puder me ajudar com esse problema.:

Numa matriz A,nxn, em que os elementos aij pode corresponder exclusivamente a 1 ou a 0, sendo que 1 indica ligação e 0 indica falta dessa(ligação) entre os vertices i e j, como eu faço para descobrir o menor caminho entre a e b, sendo estes pares ordenados de inteiros positivos, a<=n e b<=n.

Seja L = comprimento do caminho de a ate b:

Se a = b entao L = 0.

Se A(a,b) = 1 ==> L = 1 (a e b sao ligados por uma aresta)

Caso contrario, L = menor inteiro positivo n tal que o elemento (a,b) de A^n eh <> 0.

Ou seja, voce vai calculando potencias sucessivas de A = matriz de incidencia do seu grafo ateh que o elemento cujos indices correspondem ao seus dois vertices seja diferente de zero. O comprimento do seu caminho minimo serah justamente o expoente no qual isso acontece.

Um abraco,
Claudio.

 

---

Yahoo! Mail  <http://br.mail.yahoo.com/>
O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso POP3, filtro contra spam.