Not sure about what's wrong with your code is but the answer to the problem is Warshall's algorithm for graph closure. Just to brief, say we are given the adjacency matrix A[1] where A[1][i] [j] = 1 if there's an edge from i to j. Let A[k][i][j] be the the number of paths from i to j passing through only vertices numbered from 1..k. Then note that A[k][i][j] = A[k-1][i][j] + A[k-1][i][k] * A[k-1][k] [j]. i.e., the number of paths from i to j passing through only vertices numbered 1...k is equal to number of paths from i to k passing through vertices numbered 1...k-1 PLUS number of paths from i to k (with vertices 1...k-1) and k to j (with vertices 1..k-1). What we want is the A[n] matrix which has the number of paths between every pair of vertices. But by any chance A[n][i][i] > 0 for any 'i' that means there's a loop and i is a part of that loop. So this means there are infinite ways to reach i from i and hence infinite ways to reach from i to j if there's a way to reach from i to j. Hope that helps. I will paste the code once I am done with it.
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
