# -*- 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 ... :
    # on effectue P1 :
    ...
    #P2 :
    ...
    n_S=n_S+1    
     
    # on effectue P3 :
    ...                           

#test :
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.  
   
...

c.reverse()
print(c)    
              
"""