Réseau de bus : trajet le plus cher, nombre de trajets

• Même récurrence en remplaçant $\min$ par $\max$ et $+\infty$ par $-\infty$ : $M(0)=0$ et $M(j)={\max }_{i\in \mathrm{pred}(j)}\{M(i)+c(i,j)\}$. C'est possible parce que le graphe est sans circuit (sinon un trajet pourrait tourner indéfiniment).

Mmax = [0, 5, 10, 20, 30]
0--(5)-->1--(5)-->2--(10)-->3--(10)-->4

Le trajet direct $0\to 4$ coûte aussi $30$ : il y a deux trajets de coût maximum.

• Un trajet vers $j$ arrive par un prédécesseur $i$, et deux trajets arrivant par des prédécesseurs différents sont différents :

$$N(0)=1,N(j)=\sum _{i\in \mathrm{pred}(j)}N(i).$$

static long[] nombreTrajets(Liste[] Gp) { int n = Gp.length;
    long[] N = new long[n];
    N[0] = 1;                                         // le trajet réduit à 0
    for (int j = 1; j < n; j++)
        for (Liste l = Gp[j]; !vide(l); l = reste(l)) N[j] += N[premier(l)];
    return N;
}

N = [1, 1, 1, 2, 5]

Les cinq trajets vers $4$ : $0\to 4$, $0\to 1\to 4$, $0\to 1\to 2\to 4$, $0\to 3\to 4$, $0\to 1\to 2\to 3\to 4$.