#importations

#fonctions


#programme principal
#matrices d'adjacence (listes de listes)
G1 = [[0,3,5,0,0,0,0],
      [3,0,0,2,5,0,0],
      [5,0,0,3,0,5,0],
      [0,2,3,0,2,0,6],
      [0,5,0,2,0,0,3],
      [0,0,5,0,0,0,4],
      [0,0,0,6,3,4,0]]

G2 = [[0,1,1,0,0,0,0],
      [0,0,0,1,1,0,0],
      [0,0,0,1,0,1,0],
      [0,1,0,0,1,0,1],
      [0,0,0,0,0,0,0],
      [0,0,1,0,0,0,1],
      [0,0,0,1,1,0,1]]


def dic_adjacence(M):
    '''renvoie le dictionnaire des liste d'adajcences d'un graphe pondéré'''
    result={}
    n=len(M)
    for i in range(n):
        L=[]
        for j in range(n):
            if M[i][j]!=0:
                L.append((chr(65+j),M[i][j]))
        
        result[chr(65+i)]=L
    return result                     


def poids_chemin(D,ch):
    poids=0
    cont=True
    i=0
    lg=len(ch)
    try:
        for s in ch:
            D[s]
        while cont  and i<lg-1:
            cont=False

            for (s,p) in D[ch[i]]:
                if s == ch[i+1]:
                    poids+=p
                    cont =True
            i+=1
        if cont==False: 
            return -1
        else:
            return poids 
    except:
            print("un sommet n'est pas dans le graphe")




def choix_nini(D,choisi,poids):
    Pmin=10**12
    Smin=None
    for x in D:
        if not choisi[x] and poids[x] <Pmin:
            Smin=x
            Pmin=poids[x]
    return Smin
    

def mise_a_jour(x,choisi,poids,pere,D):
    for (v,p) in D[x]:
        if not choisi[v] and poids[x]+p<poids[v]:
            pere[v]=x
            poids[v]=poids[x]+p
            
        
    
    
def dijkstra(D,debut,fin):
    INFINI=10**12
    pere={}
    choisi={}
    poids={}
    for s in D:
        pere[s]=None
        choisi[s]=False
        poids[s]=INFINI
    poids[debut]=0
    choisi[debut]=True
    Sc=debut
    while not choisi[fin]:
        mise_a_jour(Sc, choisi, poids, pere, D)
        Sc=choix_nini(D, choisi, poids)
        choisi[Sc]=True
    
    S=fin
    Ch=[S]
    while pere[S]!=None:
        S=pere[S]
        Ch.append(S)
    Ch.reverse()
    return Ch,poids[fin]