python.graphs

By Vitaly Pavlenko, ago, written in Python.
URL http://pastecode.org/index.php/view/70175033
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.