""" ******************* description du graphe ********************************"""
nb_sommets = 6 # nb_sommetsest le nombre de sommets du graphe

voisins_A = [0,3,1,1000,1000,1000] # commentaire à rédiger
voisins_B = [3,0,1,2,1000,1000] 
voisins_C = [1,1,0,3,5,1000]
voisins_D = [1000,2,3,0,1,3]
voisins_E =                         # A compléter
voisins_F = [1000,1000,1000,3,1,0]
m_voisins = [voisins_A,voisins_B,voisins_C,voisins_D,voisins_E,voisins_F]  # commentaire à rédiger


"""***************** calcul du plus court chemin **********************"""
etapes=[[1000,'non determine','non'] for i in range(nb_sommets)] # initialisation de la liste stockant les étapes intermédiaires du calcul

sommet_depart=0 # indice dans la liste m_voisins du sommet de départ, 0 car le sommet de départ est A d'indice 0
dist_interm=0 # distance pour arriver au sommet sélectionnée; 0 au départ
while sommet_depart != nb_sommets-1:
    minimum=1000 #
    for n in range(1,nb_sommets):
        if etapes[n][2]=='non':
            dist=m_voisins[sommet_depart][n]
            dist_totale=dist_interm+dist
            if dist != 0 and dist_totale < etapes[n][0]:
                etapes[n][0]=dist_totale
                etapes[n][1]=sommet_depart
            if etapes[n][0]<minimum:
                minimum=etapes[n][0]
                psommet_depart=n
    sommet_depart=psommet_depart # psommet_depart = numéro du prochain sommet sélectionnée
    etapes[sommet_depart][2]='oui'
    dist_interm=etapes[sommet_depart][0]
    for i in range(1,nb_sommets):
        print(etapes[i])
    print("\n")

"""***************** reconstitution du plus court chemin, en partant du sommet d'arrivée **********************"""
chemin=[] 
sommet=nb_sommets-1
chemin.append(sommet)
while sommet != 0:
    sommet=etapes[sommet][1]
    chemin.append(sommet)
    
chemin.reverse() #inversion du chemin pour affichage dans le sens départ -> arrivée
print("le plus court chemin passe par les sommets : ",chemin,' et sa mesure est : ',etapes[nb_sommets-1][0])