# Parcours en profondeur

def DFS(G, s, visites): # récursif
    visites.add(s)
    print(s, end=' ')
    for voisin in G[s]:
        if voisin not in visites:
            DFS(G, voisin, visites)

def DFS_iter(G, s): # avec une pile
    visites = set()
    pile = [s]
    while pile: # tant que la pile n'est pas vide
        s = pile.pop()
        if s not in visites:
            visites.add(s)
            print(s, end=' ')
            for voisin in G[s]:
                pile.append(voisin)


# Parcours en largeur

from collections import deque

def BFS(G, s):
    visites = {s}
    file = deque([s])
    while file:
        s = file.popleft()
        print(s, end=' ')
        for voisin in G[s]:
            if voisin not in visites:
                file.append(voisin)
                visites.add(voisin)


# Algorithme de Dijkstra

from heapq import heappop, heappush

def plus_court_chemin(G, depart, arrivee):
    '''Renvoie le plus court chemin entre les sommets de départ et d'arrivée 
       obtenu par l'algorithme de Dijkstra.
       G est un dictionnaire qui à chaque sommet associe un dictionnaire qui
       associe à ses voisins le poids de l'arête/arc qui les relie.'''
    d = {depart: 0}      # dictionaire des distances au sommet de départ
    pred = {}            # dictionaire des prédécesseurs
    visites = set()
    file = [(0, depart)]
    
    # Construction du dictionaire des distances
    while file and arrivee not in visites:
        dmin, smin = heappop(file) # point le plus proche du depart
        if smin not in visites:
            visites.add(smin)
            for v in G[smin]:
                S = dmin + G[smin][v]
                if v not in d or S < d[v]:
                    d[v] = S
                    pred[v] = smin
                    heappush(file, (S, v))

    # Recherche du plus court chemin, s'il existe
    assert arrivee in visites, "Pas de chemin"
    chemin = [arrivee]
    s = arrivee
    while s != depart:
        s = pred[s]
        chemin.append(s)
    return chemin[::-1]