Here's the code.
void NumPathsint **a, int v) //a is the adjacency matrix and v is the number of vertices { int **t1 = new int*[v]; int **t2 = new int*[v]; for(int i = 0; i < v; ++i) { t1[i] = new int[v]; t2[i] = new int[v]; for(int j = 0; j < v; ++j) t1[i][j] = a[i][j]; } int **p1 = t1, **p2 = t2, **t; for(int k = 0; k < v; ++k) { for(int i = 0; i < v; ++i) for(int j = 0; j < v; ++j) p2[i][j] = p1[i][j] + (p1[i][k] * p1[k][j]); //to count the number of paths //swap p1, p2 t = p1; p1 = p2; p2 = t; } //if p1[i][i] != 0, then there is a path from i to i itself which is a loop so there are infinite paths from i to j if there's one path from i to j for(int i = 0; i < v; ++i) { if (p1[i][i] != 0) { p1[i][i] = -1; //-1 means loop and hence infinite paths for(int j = 0; j < v; ++j) p1[i][j] = p1[i][j] ? -1 : p1[i][j]; } } for(int i = 0; i < v; ++i) for(int j = 0; j < v; ++j) a[i][j] = p1[i][j]; //now 'a' contains the required results } --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---