N_routeurs=6
m_adjac=[[1,1,10,0,0,0],[1,1,0,22,0,0],[10,0,1,3,1,3],[0,22,3,1,4,0],[0,0,1,4,1,1],[0,0,3,0,1,1]]
Dijkstra=[] 
for i in range (N_routeurs):
    Dijkstra.append([1000000,"x","N"]) 
Routeur_select=0 
d_inter=0 
sol=1 #par défaut il y a une solution
while Routeur_select!= N_routeurs-1:
    Minimum=1000000
    for n in range(1,N_routeurs):
        if Dijkstra[n][2]=="N":
            d=m_adjac[Routeur_select][n]
            d_totale=d_inter+d
            if (d!=0 and d_totale<Dijkstra[n][0]):
                Dijkstra[n][0]=d_totale
                Dijkstra[n][1]=Routeur_select
            if Dijkstra[n][0]<Minimum:
                Minimum=Dijkstra[n][0]
                pRouteur_select=n
    if Routeur_select!=pRouteur_select:
        Routeur_select=pRouteur_select
    else:   
        sol=0 #il n'y a pas de solution 
        break
    Dijkstra[Routeur_select][2]="O"
    d_inter=Dijkstra[Routeur_select][0]
    
    # on affiche l'évolution de la liste djikstra à chaque itération
    for i in range(0,N_routeurs):
        print(Dijkstra[i])
    print("\n")

#affichage du plus court chemin
if sol==1:
    chemin_envers=[] 
    Routeur=N_routeurs-1
    chemin_envers.append(Routeur+1)
    while Routeur != 0:
        Routeur=Dijkstra[Routeur][1]
        chemin_envers.append(Routeur+1)
    print("plus court chemin, à  lire à  l'envers : ",chemin_envers)
    print("distance totale : ",Dijkstra[N_routeurs-1][0])

    chemin=[] 
    for i in range(len(chemin_envers)) :
        chemin.append(chemin_envers[len(chemin_envers)-i-1])
    
    print("plus court chemin, à  lire à  l'endroit: ",chemin)
    print("distance totale : ",Dijkstra[N_routeurs-1][0])
else:
    print("pas de solution")