最短的路wirteup

'''
以族谱为例，假如每家生两个。
flag_key为二维List，记录每代人遍历的中间结果
E3是第一代，第二代2个，再遍历第二代时flag_key增加两个LIST
第3代人4个，再遍历第三代人时flag_key增加4个LIST
'''


dic=[['FloraPrice','E11'],['FloraPrice','E9'],['FloraPrice','75D}'],['NoraFayette','E11'],['NoraFayette','E10'],['NoraFayette','E13'],['NoraFayette','E12'],['NoraFayette','E14'],['NoraFayette','E9'],['NoraFayette','E7'],['NoraFayette','E6'],['E10','SylviaAvondale'],['E10','MyraLiddel'],['E10','HelenLloyd'],['E10','KatherinaRogers'],['VerneSanderson','E7'],['VerneSanderson','E12'],['VerneSanderson','E9'],['VerneSanderson','E8'],['E12','HelenLloyd'],['E12','KatherinaRogers'],['E12','SylviaAvondale'],['E12','MyraLiddel'],['E14','SylviaAvondale'],['E14','75D}'],['E14','KatherinaRogers'],['FrancesAnderson','E5'],['FrancesAnderson','E6'],['FrancesAnderson','E8'],['FrancesAnderson','E3'],['DorothyMurchison','E9'],['DorothyMurchison','E8'],['EvelynJefferson','E9'],['EvelynJefferson','E8'],['EvelynJefferson','E5'],['EvelynJefferson','E4'],['EvelynJefferson','E6'],['EvelynJefferson','E1'],['EvelynJefferson','E3'],['EvelynJefferson','E2'],['RuthDeSand','E5'],['RuthDeSand','E7'],['RuthDeSand','E9'],['RuthDeSand','E8'],['HelenLloyd','E11'],['HelenLloyd','E7'],['HelenLloyd','E8'],['OliviaCarleton','E11'],['OliviaCarleton','E9'],['EleanorNye','E5'],['EleanorNye','E7'],['EleanorNye','E6'],['EleanorNye','E8'],['E9','TheresaAnderson'],['E9','PearlOglethorpe'],['E9','KatherinaRogers'],['E9','SylviaAvondale'],['E9','MyraLiddel'],['E8','TheresaAnderson'],['E8','PearlOglethorpe'],['E8','KatherinaRogers'],['E8','SylviaAvondale'],['E8','BrendaRogers'],['E8','LauraMandeville'],['E8','MyraLiddel'],['E5','TheresaAnderson'],['E5','BrendaRogers'],['E5','LauraMandeville'],['E5','CharlotteMcDowd'],['E4','CharlotteMcDowd'],['E4','TheresaAnderson'],['E4','BrendaRogers'],['E7','TheresaAnderson'],['E7','SylviaAvondale'],['E7','BrendaRogers'],['E7','LauraMandeville'],['E7','CharlotteMcDowd'],['E6','TheresaAnderson'],['E6','PearlOglethorpe'],['E6','BrendaRogers'],['E6','LauraMandeville'],['E1','LauraMandeville'],['E1','BrendaRogers'],['E3','TheresaAnderson'],['E3','BrendaRogers'],['E3','LauraMandeville'],['E3','CharlotteMcDowd'],['E3','flag{'],['E2','LauraMandeville'],['E2','TheresaAnderson'],['KatherinaRogers','E13'],['E13','SylviaAvondale']]
flag_key=[['E3']]   #记录遍历过程中的中间结果
finish=[87]   #记录dic中已经遍历过的元素，dic[87]=['E3','flag{']
depth=0       #第几代
while depth<92:
    find=False   #找到'75D}'退出while循环
    for i in range(len(flag_key)):
        if len(flag_key[i])!=(depth+1):  #深度小于depth，跳过
            continue
        father=flag_key[i][depth]  #i分支中的第depth代人
        if father == '75D}':
            print(flag_key[i])
            find=True   #找到'75D}'退出while循环
            break
        for j in range(len(dic)):
            if j in finish:
                continue
            elif father in dic[j]:   #  找到father的一个后代
                temp=flag_key[i].copy()#先复制父辈族谱
                if dic[j][0]==father:
                    temp.append(dic[j][1])
                else:
                    temp.append(dic[j][0])
                flag_key.append(temp)  #添加一个后代,加入族谱
                finish.append(j)  #dic中j已遍历
    if find:
        break
    depth=depth+1
#print(flag_key)