python.graphs
Go Back
—
Change Paste Viewing Options
from collections import deque
INFINITY = 1000000
def bfs(adj_matrix, distances, predecessors, s):
distances[s] = 0
Q = deque([s])
while len(Q) > 0:
v = Q.popleft()
for w, edge in enumerate(adj_matrix[v]):
if (edge == 1) and (distances[w] == INFINITY):
Q.append(w)
distances[w] = distances[v] + 1
predecessors[w] = v
n = int(input())
adj_matrix = [map(int, input().split()) for i in range(n)]
s, t = map(int, input().split())
s -= 1
t -= 1
distances = [INFINITY for i in range(n)]
predecessors = [-1 for i in range(n)]
bfs(adj_matrix, distances, predecessors, s)
if distances[t] == INFINITY:
print(-1)
else:
print(distances[t])
path = deque([t])
while predecessors[path[-1]] != -1:
path.append(predecessors[path[-1]])
print(' '.join([str(i + 1) for i in reversed(path)]))
Go Back