Suppose there is a population of 500 people, and each person knows exactly 4 other people in the population. Suppose one person gets infected with a disease, and that disease is guaranteed to infect the other 4 people that person knows in exactly 1 day's time.

Write an algorithm to determine how many days it takes for everybody to be infected, given an input adjacency matrix.

I can't figure out how to properly keep track of the days. I tried the following, but it just gives me a number close to the total number of nodes (it should be much lower):

import random
random.seed(20)

nodes = 500
num_connections = 4

# generate random graph
graph = []
for node_num in range(nodes):
  myrow = [0 for node in range(nodes - num_connections)]   [1 for connection in range(num_connections)]
  random.shuffle(myrow)
  graph.append(myrow)


days = 0
visited = [0]
queue = [0]
while queue:
  ss = queue.pop(0)
  for neighbor, is_connected in enumerate(graph[ss]):
    if is_connected == 1 and neighbor not in visited:
      visited.append(neighbor)
      queue.append(neighbor)
      days  = 1

print(days)

What am I doing wrong?

CodePudding user response：

1. find longest shortest path from first infected person to any other person, using the Dijkstra algorithm.
2. The length of this path is the number of days.

CodePudding user response：

your problem is equivalent to finding the longest shortest route in the graph. but if you want to fix your current code, I fixed it for you :)

import random

random.seed(20)

nodes = 50
num_connections = 4

# generate random graph
graph = []
for node_num in range(nodes):
    myrow = [0 for node in range(nodes - num_connections)]   [1 for connection in range(num_connections)]
    random.shuffle(myrow)
    graph.append(myrow)

days = 0
visited = [0]
queue = [0]
while len(visited) < nodes:
    patients = queue.copy()
    queue.clear()
    days  = 1
    while len(patients) > 0:
        ss = patients.pop(0)
        for neighbor, is_connected in enumerate(graph[ss]):
            if is_connected == 1 and neighbor not in visited:
                visited.append(neighbor)
                queue.append(neighbor)
    if len(queue) == 0:
        print(f'The given directional graph is not connected, after {days} days, {len(visited)} persons has been infected')
        exit()

print(days)