python.graphs

Go BackChange 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