Toutes les lignes existent — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 7)

Toutes les lignes existent

Graphes sans circuit et ordonnancement de projets · niveau 2

Énoncé

Pour toutes villes $i < j$ , il existe une ligne directe de coût $d (i, j)$ , rangé dans D[i][j] (les autres cases sont quelconques).

Donner la récurrence du coût minimum $m (j)$ d'un trajet de $0$ à $j$ .
Écrire int[][] calculerMA(int[][] D), sans construire de graphe, et donner sa complexité.
Calculer $M$ , $A$ et un trajet optimal de $0$ à $4$ pour

$d (i, j)$	$1$	$2$	$3$	$4$
$i = 0$	10	40	80	130
$1$		25	50	90
$2$			30	60
$3$				20

Corrigé

Ici $pred (j) = [0 : j]$ : $m (0) = 0$ et, pour $1 \leq j < n$ , $m (j) = min_{0 \leq i < j} {m (i) + d (i, j)}$ .
Le graphe symétrique est remplacé par une boucle sur $i$ :


static int[][] calculerMA(int[][] D) { int n = D.length;
    int[] M = new int[n], A = new int[n];
    M[0] = 0; A[0] = -1;
    for (int j = 1; j < n; j++) {
        M[j] = INFINI;
        for (int i = 0; i < j; i++)                   // pred(j) = [0:j]
            if (M[i] + D[i][j] < M[j]) { M[j] = M[i] + D[i][j]; A[j] = i; }
    }
    return new int[][] {M, A};
}

Le corps de la boucle intérieure s'exécute $0 + 1 + \dots + (n - 1) = n (n - 1) /2$ fois : $Θ (n^{2})$ , ce qui est bien $Θ (n + m)$ puisque le graphe complet a $m = n (n - 1) /2$ arcs.

Exécution :


MD = [0, 10, 35, 60, 80], AD = [-1, 0, 1, 1, 3]
0--(10)-->1--(50)-->3--(20)-->4


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