Chcę znaleźć najkrótszą drogę zgoal doroot działa wstecz

Moje dane wejściowe dlaroot jest{'4345092': ['6570646', '40586', '484']} Moje dane wejściowe dlagoal jest{'886619': ['GOAL']}

Moje dane wejściowe dlapath_holder jest wejściem, ale zostaje przekształcone nadct i jest używany do tej funkcji. Utknąłem w odniesieniu do pętli while, ponieważ tworzy ona dla mnie ścieżkę wstecz. W tej chwili nie mogę dostaćq drukować, ponieważ ta część kodu nie jest uruchomiona.dct jest zasadniczo skierowaną reprezentacją grafu, która zawiera cykle. Wydaje mi się, że nie wiem, jak zacząćGOAL i skończyć naroot węzeł. Zastanawiałem się, czy ktoś może mi pomóc to zrozumieć!

dct:

dct = 
{ '612803266': ['12408765', '46589', '5880', '31848'], 
  '8140983': ['7922972', '56008'],
  '7496838': ['612803266'], 
  '1558536111': ['7496838'], 
  '31848': ['DEADEND'], 
  '1910530': ['8140983'], 
  '242010': ['58644', '886619'], 
  '727315568': ['DEADEND'], 
  '12408765': ['DEADEND'], 
  '56008': ['DEADEND'], 
  '58644': ['DEADEND'], 
  '886619': ['GOAL'], 
  '40586': ['931', '727315568', '242010', '1910530'], 
  '5880': ['1558536111'], 
  '46589': ['DEADEND'], 
  '6570646': ['2549003','43045', '13830'],
  '931': ['299159122'],
  '484': ['1311310', '612803266'],
  '1311310': ['DEADEND'],
  '7922972': ['DEADEND']
  }

moja funkcja:

def backtrace(path_holder, root, goal):
    dct = {}
    for d in path_holder:
            dct.update(d)
    rootnode = root.keys()[0]
    goal = goal.keys()[0]
    path = []
    path.append(goal)
    q = 0
    while goal != rootnode: 
        # find key that contains goal in list
        for i in dct:   #iterate keys
            if i in dct:    # prevent repeat of path
                continue
            for j in dct[i]:    #iterate though children
                if j == goal:
                    path.append(i)
                    goal = i    # look for new goal
                    q += 1
                    print q
                    #print goal

        # append key that has goal in the list
        # set goal to be the key that was appended
        # repeat

    return path