Dijkstra qui rend les chemins

def dijkstra(G, source):
    # G[u] = liste de couples (voisin, poids), poids POSITIFS
    INF = float('inf')
    dist = {u: INF for u in G}
    pred = {u: None for u in G}
    dist[source] = 0
    restants = set(G)
    while restants:
        u = min(restants, key=lambda s: dist[s])
        if dist[u] == INF:
            break                      # les sommets restants sont inatteignables
        restants.remove(u)
        for v, poids in G[u]:
            if dist[u] + poids < dist[v]:
                dist[v] = dist[u] + poids
                pred[v] = u            # <- la seule ligne ajoutee
    return dist, pred

def chemin(pred, source, cible):
    c = []
    u = cible
    while u is not None:
        c.append(u)
        u = pred[u]
    c.reverse()
    return c if c[0] == source else None      # None : pas de chemin

Le principe. Une seule ligne suffit : chaque fois qu'on améliore la distance d'un sommet, on note par où l'on est passé. À la fin, remonter les prédécesseurs depuis la cible reconstitue le chemin — à l'envers, d'où le reverse.

Deux garde-fous. Le test c[0] == source distingue « pas de chemin » d'un chemin réel : sans lui, la fonction renverrait une liste tronquée pour un sommet inatteignable. Et l'arrêt sur dist[u] == INF évite de traiter des sommets qu'aucune arête ne relie à la source.

L'hypothèse, toujours la même : les poids doivent être positifs. Avec un poids négatif, un sommet déjà « fixé » pourrait être amélioré plus tard, et le prédécesseur mémorisé deviendrait faux.