# Exercice 2 : implantation des files de priorité
def file_prio():
    pass # TODO

def est_vide(f):
    pass # TODO

def enfiler_ou_maj(f, x, nouvelle_prio):
    pass # TODO

def defiler(f):
    pass # TODO

def test_file_prio():
    f = file_prio()
    enfiler_ou_maj(f, 'A', 10)
    enfiler_ou_maj(f, 'B', 3)
    enfiler_ou_maj(f, 'C', 7)
    enfiler_ou_maj(f, 'A', 5)
    enfiler_ou_maj(f, 'A', 20)
    enfiler_ou_maj(f, 'D', 15)
    assert(not est_vide(f))
    assert(defiler(f) == ('B', 3))
    assert(defiler(f) == ('A', 5))
    assert(defiler(f) == ('C', 7))
    assert(not est_vide(f))
    assert(defiler(f) == ('D', 15))
    assert(est_vide(f))

# Décommentez pour tester votre code de l'exercice 1
# test_file_prio()

## Exercice 3
exemple_graphe = {
    'A': [('B', 7), ('C', 4), ('D', 9)],
    'B': [('A', 7), ('C', 4), ('E', 6)],
    'C': [('A', 4), ('B', 4), ('F', 7)],
    'D': [('A', 9), ('G', 7), ('H', 1)],
    'E': [('B', 6), ('F', 3)],
    'F': [('C', 7), ('E', 3)],
    'G': [('D', 7), ('H', 4)],
    'H': [('D', 1), ('G', 4)]
}

def dijkstra(graphe, source):
    pass # TODO

def test_dijkstra():
    assert(dijkstra(exemple_graphe, 'A') == {'A': 0, 'B': 7, 'C': 4, 'D': 9, 'E': 13, 'F': 11, 'G': 14, 'H': 10} )

# Décommentez pour tester votre code de l'exercice 3:
# test_dijkstra()