Deux lignes de bus, à la main

• Base : $m(0)=0$, $m(1)=d_1(0)=5$. Puis, par $j$ croissants :

• $m(2)=\min \{m(1)+30,m(0)+20\}=\min \{35,20\}=20$ ;
• $m(3)=\min \{m(2)+10,m(1)+15\}=\min \{30,20\}=20$ ;
• $m(4)=\min \{m(3)+40,m(2)+60\}=\min \{60,80\}=60$ ;
• $m(5)=\min \{m(4)+10,m(3)+20\}=\min \{70,40\}=40$.

Donc $M=[0,5,20,20,60,40]$.

nom : M
valeurs : 0 5 20 20 60 40
colorier : 5
vert : 0..4
fleches : 4->5 3->5
legende : m(5) = min(60 + 10, 20 + 20) = 40

• On remonte : $m(5)$ est atteint par la ligne longue depuis $3$ ; $m(3)$ par la ligne longue depuis $1$ ; $m(1)$ par la ligne courte depuis $0$. Trajet $0\to 1\to 3\to 5$, de coût $5+15+20=40$. On remarque qu'il ne passe pas par la ville $4$, pourtant $m(4)=60>m(5)$.

nom : M
valeurs : 0 5 20 20 60 40
vert : 0 1 3 5
griser : 2 4
fleches : 0->1:5 1->3:15 3->5:20
legende : trajet 0 → 1 → 3 → 5, de coût 40 : la ville 4 est évitée

• On teste lequel des deux cas réalise $m(j)$ :

static void acm(int[] M, int[] D1, int[] D2, int j) {
    if (j == 0) { System.out.print("0"); return; }   // trajet réduit à la ville 0
    if (j == 1 || M[j] == M[j - 1] + D1[j - 1]) {    // dernier trajet : j-1 -> j
        acm(M, D1, D2, j - 1);                       // trajet 0 .. j-1 affiché
        System.out.printf("--(%d)-->%d", D1[j - 1], j);
    } else {                                         // dernier trajet : j-2 -> j
        acm(M, D1, D2, j - 2);                       // trajet 0 .. j-2 affiché
        System.out.printf("--(%d)-->%d", D2[j - 2], j);
    }                                                // donc trajet 0 .. j affiché
}

M = [0, 5, 20, 20, 60, 40]
Coût minimum m(5) = 40 : 0--(5)-->1--(15)-->3--(20)-->5