import numpy as np

# Pour déclencher les affichages intermédiaires
DEBUG = True 
# Graphe de test :
graphe_test = np.array([
        [0,4,np.inf,np.inf,np.inf,2],
        [4,0,2,np.inf,4,1],
        [np.inf,2,0,3,1,np.inf],
        [np.inf,np.inf,3,0,1,np.inf],
        [np.inf,4,1,1,0,5],
        [2,1,np.inf,np.inf,5,0]])


def dijkstra(g,s) :
    '''
    g : numpy array représentant la matrice d'adjacence du graphe
    s : int : entier naturel représentant l'indice du sommet de départ
    '''
    # dimension de la matrice (nombre de sommets)
    taille = g.shape[0]
    # initialisation de tableau des coûts : signification 
    #   [cout,sommet précédent,traité]
    lst  = [ [np.inf,None,False] for k in range(taille)]
    # pour l'instant, un seul sommet accessible avec distance 0
    # on met à jour le tableau des coûts
    lst[s] = [0,s,True]     # format [cout total, predecesseur, fini ou pas]
    # le sommet à partir duquel on continue ensuite
    sat = s
    # on va parcourir tous les sommets donc une boucle 
    # sur le nombre de sommets
    for k in range(taille) :
        if DEBUG :
            print("-"*20, "étape : ", k)
        # coût du sommet à traiter
        cout_sat = lst[sat][0]
        # la variable contiendra le coût minimal
        # calculé dans cette nouvel étape
        # a priori il peut ne plus y avoir rien à traiter
        plus_court = np.inf
        lst[sat][2] = True
        nsat = sat
        # on va regarder tous les sommets possibles
        for i in range(taille) :
            # on récupère le coût possible de l'arête sat ->i
            lga = ...
            # on test si le sommet est adjacent au sommet s  et pas déjà traité
            if not(lga == np.inf)  and ...  :
                # on actualise le cout de cet adjacent ...  si nécessaire
                if ... :
                    lst[i][0],lst[i][1] = ...
            # on met aussi à jour le plus court chemin à traiter ensuite
            # s'il ne s'agit pas d'un sommet déjà traité
            if lst[i][0] < plus_court and not(lst[i][2]) :
                nsat, plus_court = i,lst[i][0]
            if DEBUG :
                print("tableau : ",i, sat,nsat , lst)
                input()
        sat = nsat
    return  lst

dijkstra(graphe_test,3)