ciao, ho un po di casini con questo algoritmo:
considera un grafo orientato G=(V,E) con vertici V={1,2,3,...n}, e archi specificati dalla matrice n×n A[i,j], tale che A[i,j]=1 se (i,j)∈ E o 0 altrimenti.
problema: calcola il numero di tutti i percorsi di lunghezza 3 all'interno del grafo.
pensavo di usare l'algoritmo di chiusura transitiva ma non sono certo che sia giusto. qualcuno sa darmi qualche consiglio??
Un modo semplice che mi viene in mente è di fare 4 cicli for con 4 indici interi da 1 a n: i, j, h, k; per ogni quadrupla i, j, h, k (i va da 1 a n - 2; j da i + 1 a n - 1; k da j + 1 a n, e in piu controlli anche per k = i per considerare i cicli) verifichi se (i, j), (j, h) e (h, k) sono archi del grafo; se questo è il caso aggiungi la quadrupla ad una lista, per indicare un nuovo cammino di tre archi.
Permessi di invio
Rispondi quotando