Déjà, il faut remarquer que le graphe est acyclique.
Du coup, on peut faire un tri topologique dessus.
C'est à dire que chaque arête va d'un sommet vers un sommet plus grand selon cet ordre.
A partir de là, c'est facile de compter le nombre de chemins.
En pseudo-code.
fonction nb_chemins(graphe, source, dest):
initialiser un tableau t de graphe.len() éléments à 0
t[source] = 1
pour chaque sommet i du graphe selon l'ordre topologique
pour chaque voisin j de i
t[j] += t[i]
renvoyer t[dest]
Pour la partie 2, on peut le trouver avec la formule suivante
[^] # Re: Jour 11
Posté par Guillaume.B . En réponse au journal Advent of Code 2025. Évalué à 1.
Déjà, il faut remarquer que le graphe est acyclique.
Du coup, on peut faire un tri topologique dessus.
C'est à dire que chaque arête va d'un sommet vers un sommet plus grand selon cet ordre.
A partir de là, c'est facile de compter le nombre de chemins.
En pseudo-code.
Pour la partie 2, on peut le trouver avec la formule suivante
c(svr, dac) * c(dac, fft) * c(fft, out) + c(svr, fft) * c(fft, dac), c(dac, out)où
c(a, b)est le nombre de chemins deaàb.sachant qu'une des parties de la somme est forcément nulle.
50 microsecondes pour les deux parties.