Code to find the shortest path in Breadth First Search

Question

#Breadth First Search

graph = {
    'S' : ['A','B'],
    'A' : ['B','C','D'],
    'B' : ['C'],
    'C' : ['D'],
    'D' : []
}
visited = []
queue = []
goal = 'D'
def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)
  while queue : 
    s = queue.pop(0)
    print(s, end = "\n")
    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)
        if goal in visited:
          break
bfs(visited,graph,'S')          

#above mentioned code is for path of traversal. Can anyone please give the code to find the shortest path. The output of the above code is S A B C D

Answer 1

Since all edges have same weight or no weight you can apply BFS to find the shortest path in the following way - the first time the node is encountered it means that the path to it is the shortest one, so for every visited vertex you can maintain the previous one which lead to it and then restore the path when the goal vertex is encountered:

visited_paths = {}
queue = []
goal = 'D'
def bfs(visited, graph, node):
  visited[node] = node # path to start includes start
  queue.append(node)
  while queue: 
    s = queue.pop(0)
    if(s == goal):
        break

    for n in graph[s]:
        if n not in visited:
            queue.append(n)
            visited[n] = s # set previous node when node is first encountered

  if goal in visited:
    # restore the path
    path = [goal]
    curr = goal
    while curr != node:
       curr = visited[curr]
       path.append(curr)
    path.reverse() # reverse path to get correct order
    print(path)
  else:
    print("No path")

bfs(visited_paths,graph,'S')