create a program that says the minimum amount of contacts

user_16615299 0
Viewed 36

Given a graph describing the relationships of the social network, create a program that tells the minimum amount of contacts to reach John.

Input:

The first line of the input indicates how many are the n vertices of the graph (2 ≤ n ≤ 100). The next n lines each represent the information of a vertex in the format: id,A,v1,v2,⋯,vA, where id is an integer identifying the vertex, A is the number of edges connected to this vertex, and each vi ≠ id is an integer identifying a vertex adjacent to id. The last line has two ids, separated by space, that represent you and John, respectively.

Exit:

Present the minimum amount of contacts needed to reach John, if possible, the message "Forevis alonis..." otherwise.

Observation: Each network user is represented by a unique id. In the first example, John is already one of your contacts. In the second case, you have to go through users 2 and 3 to reach the idol. In the latter case, it is not possible to contact you...

enter image description here

My code for this problem so far has been this as I haven't been able to solve the problem. Code:

graph = {}
for _ in range(int(input())):
  v, A, *neighbor = map(int,(input().split()))
  graph[v] = neighbor
I, John = map(int, input().split())

def shortest_way(origin, destination, path=[]):
  path.append(origin)
  if origin == destination:
    return path
  shorter = [] 
  for neighbors in graph[origin]:
    if neighbors not in path:
      outro_caminho = shortest_way(neighbors.destination.path[:])
graph python-3.x python
1 Answers

One possible solution is to use one list as the current path and then once the destination is reached, to store save it in paths so that at the end you can compare all possible solutions and return the shortest one.

def shortest_way(origin, destination, path, paths):
  if origin == destination:
    path += [destination]
    paths.append(path)
    return paths
  for neighbor in graph[origin]:
    if neighbor not in path:
      shortest_way(neighbor, destination, path+[origin], paths)
  return paths

paths = shortest_way(I, John, [], [])
if not paths:
  print("Forevis alonis...")
print("shortest path =", min([len(i) for i in paths]))
user_178294510
Related