# -*- coding: utf-8 -*-
"""
Created on Tue Jul  1 17:40:12 2014

@author: utilisateur
"""
from math import inf


Table_poids = [[0, 4,8,inf,inf,inf,inf, inf , inf , inf ],
             [4,0,7, 18,21,inf,inf , inf , inf , inf],
             [8,7,0,10,inf,25,inf , inf , inf , inf],
             [inf,18,10,0,15,12,31 ,inf , inf , inf],
            [inf,21,inf,15,0,10,17 , 11 , inf , inf],
            [inf,inf,25,12,10,0,7 , inf , inf , 9],
             [inf,inf,inf,31,17,7,0 , inf , 7 , inf],
             [inf,inf,inf,inf,11,inf,inf, 0 , 8 , inf ],
             [inf,inf,inf,inf,inf,inf,7, 8 , 0 , inf ],
             [inf,inf,inf,inf,inf,9,inf, inf , inf , 0]]
             




n=len(Table_poids)# ordre du graphe

#Initialisation des variables de l'algorithme de Dijkstraa


sommetDep = 0 # numéro du sommet de départ 

#listeS[i] vaut 0 ou 1 selon que i est dans S
listeS = [0 for i in range(n)] 
listeS[sommetDep] = 1
n_S=1 #nombre d'éléments dans S

#listeDA : liste des d_A(i)
listeDA = [Table_poids[sommetDep][i] for i in range(n)]
#Remarque : permet aussi de savoir si un élément est dans S'

#listeAnte : liste des antécédents sur le plus court chemin
 #           -1 si pas encore de chemin trouvé

listeAnte =  [-1 for i in range(n)] 
for i in range(n):
    if Table_poids[sommetDep][i] != 0 and Table_poids[sommetDep][i] < inf:
        listeAnte[i] = sommetDep



#Algorithme
while n_S < n :
    dA_min = inf       # début P1
    for i in range(n):
        if listeS[i] == 0 and listeDA[i] < dA_min : 
            dA_min = listeDA[i]
            x_0 = i # fin P1
    listeS[x_0] = 1       #P2
    n_S=n_S+1         
    for i in range(n):  # début P3
        if listeS[i] == 0 and listeDA[x_0] + Table_poids[x_0][i] < listeDA[i] :
                listeDA[i]=listeDA[x_0] + Table_poids[x_0][i] 
                listeAnte[i] = x_0                           #fin P3


print(listeDA)    
            
#chemin le plus court de A un sommet   
s = 9 # On part du point d'arrivée J        
c=[s]# c est destiné à recevoir ce chemin.     
while  s!=0 :
    s = listeAnte[s]
    c = c+[s]
c.reverse()
print(c)