Aller au contenu
Réussir mon BTS SIO

Tape une notion, une commande ou le nom d'une épreuve.

Par exemple

Exercice 6 / 8Difficile

Le plus court chemin avec Dijkstra

À toi

Six routeurs A à F sont reliés par des liens orientés. La valeur d'un arc est le coût du lien.

ArcA → BA → CC → BB → DC → DC → ED → ED → FE → F
Coût4125810261

Applique l'algorithme de Dijkstra depuis A.

  1. Donne le coût minimal de A vers B, D, E et F.
  2. Pour reconstruire le meilleur chemin vers F, donne le sommet d'où l'on vient pour arriver en F, puis en E, puis en D.

Graphes et ordonnancement

Vocabulaire d'un graphe orienté

Un graphe orienté a des sommets et des arcs (x, y), de x vers y. Γ⁺(x) est l'ensemble des successeurs de x, Γ⁻(x) celui de ses prédécesseurs. Le nombre de successeurs s'appelle aussi le demi-degré extérieur, le nombre de prédécesseurs le demi-degré intérieur. Une source n'a aucun prédécesseur, un puits aucun successeur. La somme des nombres de successeurs est égale au nombre d'arcs.

Matrice d'adjacence et chemins

Ligne = origine, colonne = extrémité. La ligne de x donne ses successeurs, sa colonne ses prédécesseurs, et chaque 1 est un arc.

Le coefficient (i, j) de Mᵖ est le nombre de chemins de longueur p de i vers j. Dans la puissance booléenne M^[p], il vaut 1 s'il en existe au moins un.

Astuce de calcul : la ligne i de M² est la somme des lignes de M des successeurs de i. Avec les arcs A → B, A → C, B → C et C → A :

text
      A  B  C              A  B  C
M = [ 0  1  1 ]  A    M² = [ 1  0  1 ]  A : ligne B + ligne C de M
    [ 0  0  1 ]  B         [ 1  0  0 ]  B : ligne C de M
    [ 1  0  0 ]  C         [ 0  1  1 ]  C : ligne A de M

Le 1 en (A, A) de M² est le circuit A → C → A, de longueur 2.

La fermeture transitive : Roy-Warshall

La fermeture transitive ajoute un arc x → y chaque fois qu'il existe un chemin de x vers y. Sa matrice M̂ se calcule ainsi : pour chaque sommet k, dans l'ordre, chaque ligne qui a un 1 dans la colonne k reçoit la somme booléenne de la ligne k, en utilisant la matrice telle qu'elle est à ce moment-là. Pour les arcs A → B et B → C : à l'étape k = B, la ligne A (qui a un 1 en colonne B) devient (0 1 0) ⊕ (0 0 1) = (0 1 1). On ajoute l'arc (A, C).

Les arcs à ajouter sont les 1 de M̂ qui étaient des 0 dans M. Un 1 sur la diagonale de M̂ signale un sommet qui appartient à un circuit.

Les niveaux d'un graphe sans circuit

Niveau 0 : les sommets sans prédécesseur. On les raye ; les sommets dont tous les prédécesseurs sont rayés forment le niveau 1, et ainsi de suite. Le niveau d'un sommet vaut un de plus que le plus grand niveau de ses prédécesseurs.

Le plus court chemin : Dijkstra

Chaque sommet porte une marque : la meilleure valeur connue depuis le départ, et le sommet d'où l'on vient. Au départ, 0 pour le sommet de départ, ∞ pour les autres. Puis on répète :

  1. on fixe le sommet non fixé de plus petite marque ;
  2. pour chacun de ses successeurs y non fixé, si marque(x) + v(x, y) est strictement plus petit que la marque de y, on la remplace et on note « vient de x ».

Avec A → B (5), A → C (2) et C → B (1) : on fixe A, B reçoit 5 (A) et C 2 (A) ; on fixe C, B passe à 2 + 1 = 3 (C) ; on fixe B. Le meilleur chemin vers B est A, C, B, de valeur 3. On le reconstruit en remontant les « vient de » depuis l'arrivée.

L'ordonnancement par la méthode MPM

Chaque tâche est un sommet ; on ajoute Début et Fin. d(x) est la durée de x.

  • Date au plus tôt, de gauche à droite : t(Début) = 0 et t(x) = max [ t(p) + d(p) ] sur les tâches antérieures p. t(Fin) est la durée minimale du projet.
  • Date au plus tard, de droite à gauche : T(Fin) = t(Fin) et T(x) = min [ T(s) ] − d(x) sur les tâches suivantes s.
  • Une tâche est critique si t(x) = T(x). Le chemin critique va de Début à Fin par des tâches critiques : c'est le chemin le plus long.
  • Marge totale MT(x) = T(x) − t(x) : retard possible sans retarder la fin du projet.
  • Marge libre ML(x) = min [ t(s) ] − t(x) − d(x) : retard possible sans décaler aucune tâche suivante. Pour une tâche reliée à Fin, on prend t(Fin).
  • Marge certaine MC(x) = min [ t(s) ] − max [ T(p) + d(p) ] − d(x), ou 0 si c'est négatif. Sans tâche antérieure, le max est remplacé par 0.

Exemple : A (3 jours), B (2 jours, après A), C (4 jours, après A), D (1 jour, après B et C). t(A) = 0, t(B) = t(C) = 3, t(D) = max [ 3 + 2 ; 3 + 4 ] = 7, t(Fin) = 8. T(D) = 7, T(B) = 7 − 2 = 5, T(C) = 7 − 4 = 3, T(A) = min [ 5 ; 3 ] − 3 = 0. Chemin critique : A, C, D. MT(B) = 5 − 3 = 2 et ML(B) = 7 − 3 − 2 = 2.

Tes réponses

Connecte-toi pour faire cet exercice

C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.

Le site garde ton nom et ton email, rien d'autre. Tes données