# python.graphs

By Vitaly Pavlenko, ago, written in Python.
Download Paste or View RawExpand paste to full width of browser | Change Viewing Options
1. from collections import deque
2.
3. INFINITY = 1000000
4.
5. def bfs(adj_matrix, distances, predecessors, s):
6.     distances[s] = 0
7.     Q = deque([s])
8.     while len(Q) > 0:
9.         v = Q.popleft()
10.         for w, edge in enumerate(adj_matrix[v]):
11.             if (edge == 1) and (distances[w] == INFINITY):
12.                 Q.append(w)
13.                 distances[w] = distances[v] + 1
14.                 predecessors[w] = v
15.
16.
17. n = int(input())
18. adj_matrix = [map(int, input().split()) for i in range(n)]
19. s, t = map(int, input().split())
20. s -= 1
21. t -= 1
22. distances = [INFINITY for i in range(n)]
23. predecessors = [-1 for i in range(n)]
24.
25. bfs(adj_matrix, distances, predecessors, s)
26.
27. if distances[t] == INFINITY:
28.     print(-1)
29. else:
30.     print(distances[t])
31.     path = deque([t])
32.     while predecessors[path[-1]] != -1:
33.         path.append(predecessors[path[-1]])
34.     print(' '.join([str(i + 1) for i in reversed(path)]))

Here you can reply to the paste above

Make Private Feeling clever? Set some advanced options.