infinity = float('inf')

# Le dictionnaire d'adjacence du graphe

g1 = {
     'a': [ ('b', 5), ('d', 4)],
     'b': [ ('a', 5), ('c', 1), ('e', 3)],
     'c': [('b', 1), ('d', 3), ('e', 1)],
     'd': [('a', 4), ('c', 3), ('e', 4)],
     'e': [('b', 3), ('c', 1), ('d', 4)]
}

g3 = {
    1:[(2,7),(3,9),(6,14)],
    2:[(1,7),(3,10),(4,15)],
    3:[(1,9),(2,10),(4,11),(6,2)],
    4:[(2,15),(3,11),(5,6)],
    5:[(4,6),(6,9)],
    6:[(1,14),(3,2),(5,9)]
    }
##
def init(g):
    pass


def extraire_min(salle_attente, dist):
    '''renvoie le sommet de salle_attente de distance minimale'''
    dmin = infinity
    pass


t = [4, 10, 12]
dist = {4:11, 10:3, 12:8, 1:45, 25:2}
print(extraire_min(t, dist))

##
def dijkstra1(G, source, cible):
    '''G est un graphe pondéré à poids positifs. Renvoie la distance minimale entre source et cible s'ils sont dans la même composante connexe du graphe.'''
    salle_attente = [source] # liste implémentant la salle d'attente: les gris
    pass

dijkstra1(g1, 'a', 'e') # on trouve 7
dijkstra1(g3, 1, 6) # on trouve 11

## Implémentation 2 avec renvoi du chemin

def chemin(parents, source, cible):
    pass


parents = {0: None, 9: 0, 2: 0, 1: 9, 3: 2, 5: 2, 6: 2}
chemin(parents, 0, 3)

def dijkstra2(G, source, cible):
    '''G est un graphe pondéré à poids positifs. Renvoie la distance minimale entre source et cible s'ils sont dans la même composante connexe du graphe.'''
    pass

dijkstra2(g1, 'a', 'e') # on trouve (7, ['a', 'b', 'c', 'e'])
dijkstra2(g3, 1, 6) # on trouve (11, [1, 3, 6])