





__lowerCamelCase			:	Optional[Any]					    =	{
    """A""": ["""B""", """C""", """E"""],
    """B""": ["""A""", """D""", """E"""],
    """C""": ["""A""", """F""", """G"""],
    """D""": ["""B"""],
    """E""": ["""A""", """B""", """D"""],
    """F""": ["""C"""],
    """G""": ["""C"""],
}



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase				,  _lowerCAmelCase	)		->					list[str]:
 UpperCamelCase      :   Tuple			      =  set()
 # keep track of all the paths to be checked
 UpperCamelCase      :   Dict			      =  [[start]]

 # return path if start is goal
 if start == goal:
  return [start]

 # keeps looping until all possible paths have been checked
 while queue:
  # pop the first path from the queue
  UpperCamelCase      :   List[str]			      =  queue.pop(0	)
  # get the last node from the path
  UpperCamelCase      :   Tuple			      =  path[-1]
  if node not in explored:
   UpperCamelCase      :   Optional[Any]			      =  graph[node]
   # go through all neighbour nodes, construct a new path and
   # push it into the queue
   for neighbour in neighbours:
    UpperCamelCase      :   Union[str, Any]			      =  list(_lowerCAmelCase	)
    new_path.append(_lowerCAmelCase	)
    queue.append(_lowerCAmelCase	)
    # return path if neighbour is goal
    if neighbour == goal:
     return new_path

            # mark node as explored
   explored.add(_lowerCAmelCase	)

    # in case there's no path between the 2 nodes
 return []



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase				,  _lowerCAmelCase	)		->					int:
 if not graph or start not in graph or target not in graph:
  return -1
 if start == target:
  return 0
 UpperCamelCase      :   str			      =  [start]
 UpperCamelCase      :   Any			      =  set(_lowerCAmelCase	)
 # Keep tab on distances from `start` node.
 UpperCamelCase      :   Dict			      =  {start: 0, target: -1}
 while queue:
  UpperCamelCase      :   Union[str, Any]			      =  queue.pop(0	)
  if node == target:
   UpperCamelCase      :   int			      =  (
       dist[node] if dist[target] == -1 else min(dist[target]				,  dist[node]	)
   )
  for adjacent in graph[node]:
   if adjacent not in visited:
    visited.add(_lowerCAmelCase	)
    queue.append(_lowerCAmelCase	)
    UpperCamelCase      :   Optional[Any]			      =  dist[node] + 1
 return dist[target]


if __name__ == "__main__":
    print(bfs_shortest_path(demo_graph, """G""", """D"""))  # returns ['G', 'C', 'A', 'B', 'D']
    print(bfs_shortest_path_distance(demo_graph, """G""", """D"""))  # returns 4







__lowerCamelCase			:	Any					    =	9.8_0_6_6_5



def 						A_							(	_lowerCAmelCase				,  _lowerCAmelCase				,  _lowerCAmelCase = g	)		->					float:

 if fluid_density <= 0:
  raise ValueError("Impossible fluid density"	)
 if volume < 0:
  raise ValueError("Impossible Object volume"	)
 if gravity <= 0:
  raise ValueError("Impossible Gravity"	)

 return fluid_density * gravity * volume


if __name__ == "__main__":
    import doctest

    # run doctest
    doctest.testmod()
