bfs_all_paths.py

# this code prints all the shortest paths possible from start node
# to end node in UNDIRECTED, UNWEIGHTED graph
class node:
    def __init__(self,val,path,dis):
        self.val = val
        self.path = path
        self.dis = dis
ans = []
graph =[
[0, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 1],
[0, 0, 0, 1, 0, 1, 1],
[0, 1, 1, 0, 1, 0, 0],
[0, 0, 0, 1, 1, 0, 0]]
n = len(graph)
distance = [float('inf')]*n # n is number of nodes
end = 6
queue = []
start = 0
queue.append(node(start,[start],0))
min_dis = float('inf')
distance[start]=0
while(queue):
    s = queue.pop(0)
    if(s.val==end):
        min_dis = s.dis
        ans.append(s)
    if(s.dis>min_dis):
        pass
    else:
        for i in range(n):
            if(graph[s.val][i]==1 and distance[i]>=s.dis+1):
                queue.append(node(i,s.path+[i],s.dis+1))
                distance[i] = s.dis+1
for i in ans:
    print i.path