Too late but for the sake of explanation: the DFS algorithms and the Dynamic Programming tehcniques are useful to know but the problem of counting (not enumerating) different paths in an oriented graph can be simply solved in O(n^3) time by these cycles:
for(i = 0 to N)
for(j =0 to N)
for(k = 0 to N)
path[i][j] += path[i][k] * path [k][j]
where path[][] is the matrix mapping any vertex to each other setting "0" if there is no edge between them and "1" if they are connected. The result will come in few seconds. Thanks to this post: stackoverflow.com/questions/164213...
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Too late but for the sake of explanation: the DFS algorithms and the Dynamic Programming tehcniques are useful to know but the problem of counting (not enumerating) different paths in an oriented graph can be simply solved in O(n^3) time by these cycles:
for(i = 0 to N)
for(j =0 to N)
for(k = 0 to N)
path[i][j] += path[i][k] * path [k][j]
where path[][] is the matrix mapping any vertex to each other setting "0" if there is no edge between them and "1" if they are connected. The result will come in few seconds. Thanks to this post:
stackoverflow.com/questions/164213...