Advertisement
viligen

shortest_path_unweightedGraph_bfs

Aug 9th, 2022
492
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.82 KB | None | 0 0
  1. from collections import deque
  2.  
  3.  
  4. nodes = int(input())
  5. edges = int(input())
  6.  
  7. graph = [[] for _ in range(nodes + 1)]
  8.  
  9. for _ in range(edges):
  10.     source, destination = [int(x) for x in input().split()]
  11.     graph[source].append(destination)
  12.  
  13. start_node = int(input())
  14. end_node = int(input())
  15.  
  16. visited = [False] * (nodes + 1)
  17. parent = [None] * (nodes + 1)
  18.  
  19. visited[start_node] = True
  20. q = deque([start_node])
  21.  
  22. while q:
  23.     node = q.popleft()
  24.     if node == end_node:
  25.         break
  26.  
  27.     for child in graph[node]:
  28.         if visited[child]:
  29.             continue
  30.         visited[child] = True
  31.         q.append(child)
  32.         parent[child] = node
  33.  
  34. path = deque()
  35. node = end_node
  36. while node is not None:
  37.     path.appendleft(node)
  38.     node = parent[node]
  39.  
  40. print(f'Shortest path length is: {len(path)-1}')
  41. print(*path)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement