Réseau de bus : trajet de coût minimum

• Supposons le problème résolu : un trajet optimal vers $j\ne 0$ arrive sur $j$ par une dernière ligne $i\to j$, avec $i\in \mathrm{pred}(j)$, et sa partie de $0$ à $i$ est elle-même optimale (principe d'optimalité). D'où :

$$m(0)=0,\forall j,1\le j<n:m(j)=\underset{i\in \mathrm{pred}(j)}{\min }\{m(i)+c(i,j)\}.$$

Si $\mathrm{pred}(j)$ est vide, le minimum vaut $+\infty$ : $j$ est inaccessible.

• Tous les prédécesseurs de $j$ ont un numéro $i<j$ (les lignes vont de $i$ à $j>i$, la numérotation est isotone) : quand on calcule $m(j)$ par $j$ croissants, toutes les valeurs $m(i)$ utiles sont connues.
• On parcourt les prédécesseurs dans le graphe symétrique et l'on mémorise l'argument du minimum.

static final int INFINI = Integer.MAX_VALUE / 2;

static int[][] calculerMA(Liste[] Gp, int[][] C) { int n = Gp.length;
    int[] M = new int[n], A = new int[n];
    M[0] = 0; A[0] = -1;                              // base
    for (int j = 1; j < n; j++) {                     // par j croissants
        M[j] = INFINI; A[j] = -1;
        for (Liste l = Gp[j]; !vide(l); l = reste(l)) { int i = premier(l);
            if (M[i] + C[i][j] < M[j]) {              // meilleur trajet arrivant par i
                M[j] = M[i] + C[i][j]; A[j] = i;
            }
        }
    }                                                 // M[j] = m(j), A[j] = a(j)
    return new int[][] {M, A};
}

La valeur $+\infty$ est Integer.MAX_VALUE / 2, pour que $m(i)+c(i,j)$ ne dépasse pas la capacité des int. Chaque sommet et chaque arc est touché une fois : $\Theta (n+m)$.

• On affiche d'abord le trajet jusqu'à $a(j)$, puis la dernière ligne :

static void acm(int[] A, int[][] C, int j) {
    if (j == 0) { System.out.print("0"); return; }   // trajet réduit à 0 : affiché
    acm(A, C, A[j]);                                 // trajet de 0 à a(j) affiché
    System.out.printf("--(%d)-->%d", C[A[j]][j], j); // puis la ligne a(j) --> j
}

• Exécution :

M = [0, 5, 10, 20, 25], A = [-1, 0, 1, 2, 1]
0--(5)-->1--(20)-->4
0--(5)-->1--(5)-->2--(10)-->3

nom : M
valeurs : 0 5 10 20 25
vert : 0 1 4
fleches : 0->1 1->2 2->3 1->4
legende : flèches de a(j) vers j ; en vert : le trajet 0, 1, 4 (coût 25)

Vers $4$, le trajet direct ($30$) est battu par $0\to 1\to 4$ ($25$) ; vers $3$, la ligne directe ($20$) est à égalité avec $0\to 1\to 2\to 3$ : l'inégalité stricte garde le premier prédécesseur examiné.