Skip to content

Instantly share code, notes, and snippets.

@tatianass
Created December 15, 2017 05:22
Show Gist options
  • Save tatianass/afa784a19fdf7c668b7c55ef87f1a439 to your computer and use it in GitHub Desktop.
Save tatianass/afa784a19fdf7c668b7c55ef87f1a439 to your computer and use it in GitHub Desktop.
Count all possible walks from a source to a destination with exactly k edges based on http://www.geeksforgeeks.org/count-possible-paths-source-destination-exactly-k-edges/
def count_walks(graph, u, v, k):
if(k == 0 and u == v): return 1
if(k == 1 and graph[u][v]): return 1
if(k <= 0): return 0
count = 0
for i in range(0, 5):
if(graph[u][i]):
count += count_walks(graph, i, v, k-1)
return count
graph = [[0, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[0, 1, 0, 0, 0]]
k = 4
u = 0
v = 2
print(count_walks(graph, u, v, k))
k = 3
u = 2
v = 2
if(u == v):
k += 1
print(count_walks(graph, u, v, k))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment