Trajet d'au plus k lignes — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 7)

Trajet d'au plus

k

lignes

Graphes sans circuit et ordonnancement de projets · niveau 3 (difficile)

Énoncé

Un voyageur refuse de changer de bus trop souvent : il veut un trajet de coût minimum de $0$ à $n - 1$ empruntant au plus $k$ lignes directes.

On note $m (j, k)$ le coût minimum d'un trajet de $0$ à $j$ d'au plus $k$ lignes. Donner la base ( $k = 0$ ) et l'hérédité.
Écrire le programme qui calcule le tableau $M [0 : K + 1] [0 : n]$ . Quelle est sa complexité ?
Sur le réseau de l'exercice 7.4, donner $m (4, k)$ pour $k = 0, 1, 2, 3$ .

Corrigé

Avec $0$ ligne, on reste en $0$ : $m (0, 0) = 0$ et $m (j, 0) = + \infty$ pour $j \neq = 0$ . Pour $k \geq 1$ , un trajet optimal d'au plus $k$ lignes vers $j$ soit utilise au plus $k - 1$ lignes, soit arrive par une dernière ligne $i \to j$ précédée d'un trajet d'au plus $k - 1$ lignes :

$m (j, k) = min (m (j, k - 1), i \in pred (j) min {m (i, k - 1) + c (i, j)}) .$

Calcul par $k$ croissants (la ligne $k$ ne dépend que de la ligne $k - 1$ ) :


static int[][] auPlusK(Liste[] Gp, int[][] C, int K) { int n = Gp.length;
    int[][] M = new int[K + 1][n];
    Arrays.fill(M[0], INFINI); M[0][0] = 0;           // base k = 0
    for (int k = 1; k < K + 1; k++)
        for (int j = 0; j < n; j++) {
            M[k][j] = M[k - 1][j];                    // au plus k-1 lignes
            for (Liste l = Gp[j]; !vide(l); l = reste(l)) { int i = premier(l);
                M[k][j] = Math.min(M[k][j], M[k - 1][i] + C[i][j]); // dernière ligne i --> j
            }
        }
    return M;
}

Chaque ligne du tableau coûte $Θ (n + m)$ : la complexité est $Θ (K (n + m))$ .

Exécution :


k=0 : [0, inf, inf, inf, inf]
k=1 : [0, 5, inf, 20, 30]
k=2 : [0, 5, 10, 20, 25]
k=3 : [0, 5, 10, 20, 25]

Avec une seule ligne, seul le trajet direct ( $30$ ) est possible ; dès deux lignes, on atteint l'optimum $25$ de l'exercice 7.4.