Plus court chemin en nombre d'arêtes

On effectue un BFS en mémorisant, pour chaque sommet visité, le sommet prédécesseur ; on remonte ensuite ces prédécesseurs depuis l'arrivée.

from collections import deque

def plus_court_chemin(G, depart, arrivee):
    if depart == arrivee:
        return [depart]
    predecesseur = {depart: None}
    file = deque([depart])
    while file:
        u = file.popleft()
        for v in G[u]:
            if v not in predecesseur:
                predecesseur[v] = u
                if v == arrivee:
                    # reconstruction du chemin
                    chemin = [arrivee]
                    while predecesseur[chemin[-1]] is not None:
                        chemin.append(predecesseur[chemin[-1]])
                    chemin.reverse()
                    return chemin
                file.append(v)
    return None

G = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print(plus_court_chemin(G, 0, 4))   # [0, 1, 3, 4] ou [0, 2, 3, 4]

La complexité est $O(n+m)$, celle d'un BFS, plus la reconstruction du chemin en $O(n)$.