Graphe valué et chemin optimal en longueur et en valeur

Un graphe valué (ou pondéré) est un graphe dont chaque arc porte un nombre, sa valeur : une distance, une durée, un coût. Un chemin optimal est le meilleur chemin entre deux sommets selon un critère : le plus petit nombre d'arcs (optimal en longueur), ou la plus petite, parfois la plus grande, somme des valeurs (optimal en valeur). Ce chapitre montre que ces deux critères donnent des chemins différents, énonce le principe qui rend les calculs possibles (tout morceau d'un chemin optimal est optimal) et donne la méthode par niveaux pour un graphe sans circuit. Le chapitre 7 traite le cas général avec l'algorithme de Dijkstra.

Graphe valué, longueur et valeur d'un chemin

Dans un graphe valué, chaque arc (x, y) a une valeur v(x, y), qu'on écrit sur la flèche. La valeur (ou poids) d'un chemin est la somme des valeurs de ses arcs. Il ne faut pas la confondre avec sa longueur, qui reste le nombre d'arcs.

Exemple. Un technicien se déplace entre six sites A, B, C, D, E, F d'une entreprise. Les trajets possibles et leurs durées, en minutes, sont donnés par les arcs suivants (le graphe est sans circuit, car les trajets s'enchaînent dans le sens de la tournée) :

Quelques chemins de A vers F :

Le chemin qui a le moins d'arcs n'est pas le moins coûteux : ici, le chemin de plus petite valeur est aussi l'un des plus longs.

Chemin optimal en longueur

Un chemin est optimal en longueur s'il a le plus petit nombre d'arcs possible. Deux méthodes, toutes deux déjà vues :

• avec les puissances de la matrice d'adjacence : la plus petite longueur d'un chemin de i vers j est le plus petit entier p tel que le coefficient (i, j) de M^[p] (ou de Mᵖ) soit non nul ;
• en « couches » : on marque le départ à 0, ses successeurs à 1, les successeurs de ceux-ci non encore marqués à 2, et ainsi de suite. La marque d'un sommet est sa distance en nombre d'arcs au départ. C'est le parcours en largeur du cours d'algorithmique.

Pour notre graphe : A est marqué 0 ; B et C, 1 ; D et E, 2 ; F, 3. La plus petite longueur d'un chemin de A vers F est 3, atteinte par trois chemins : (A, B, D, F), (A, C, D, F) et (A, C, E, F).

En réseau, c'est le critère du protocole de routage RIP, qui compte les sauts (le nombre de routeurs traversés) et choisit la route qui en a le moins.

Chemin optimal en valeur et principe d'optimalité

Un chemin est optimal en valeur s'il a la plus petite valeur parmi tous les chemins entre les mêmes sommets (on parle de chemin minimal), ou, selon le problème, la plus grande (chemin maximal). Le programme insiste sur une propriété :

La raison est simple : si l'on trouvait un chemin meilleur de C vers D, on le mettrait à la place de (C, B, D) dans le grand chemin, et on obtiendrait un chemin de A vers F encore meilleur, ce qui est impossible. C'est le principe d'optimalité de Richard Bellman (1957), qui fonde tous les algorithmes de plus court chemin : pour connaître le meilleur chemin jusqu'à F, il suffit de connaître les meilleurs chemins jusqu'aux prédécesseurs de F.

La méthode par niveaux (graphe sans circuit)

Quand le graphe est sans circuit, le principe d'optimalité donne une méthode très simple :

1. Range les sommets par niveaux (chapitre 5).
2. Donne la marque 0 au sommet de départ.
3. Traite les sommets niveau par niveau. Pour chaque sommet x, calcule, pour chacun de ses prédécesseurs p déjà marqués, la valeur « marque de p + v(p, x) ». La marque de x est la plus petite de ces valeurs (pour un chemin minimal) ou la plus grande (pour un chemin maximal). Note quel prédécesseur la donne.
4. Remonte le chemin depuis l'arrivée en suivant les prédécesseurs notés.

L'ordre par niveaux garantit que, quand on traite x, tous ses prédécesseurs sont déjà marqués définitivement.

Exemple : chemin minimal de A vers F. Les niveaux sont N₀ = {A}, N₁ = {C}, N₂ = {B}, N₃ = {D}, N₄ = {E}, N₅ = {F} (C est avant B, à cause de l'arc C → B).

On remonte depuis F : F vient de E, E de D, D de B, B de C, C de A. Le chemin minimal est (A, C, B, D, E, F), de valeur 12 : le technicien met au mieux 12 minutes.

Exemple : chemin maximal de A vers F. Même tableau, en gardant à chaque ligne la plus grande valeur.

Le chemin maximal est (A, C, D, F), de valeur 16. À la ligne E, il y a égalité : deux chemins de valeur 12 mènent à E, mais ce n'est pas eux qui donnent le maximum en F.

Ce que cela donne en informatique

• Routage : RIP choisit la route optimale en longueur (le moins de sauts), OSPF la route optimale en valeur, la valeur d'un lien étant un coût d'autant plus faible que son débit est élevé. Les deux peuvent choisir des routes différentes entre les mêmes routeurs.
• Itinéraires : un GPS cherche le chemin de valeur minimale, la valeur étant la durée estimée du trajet.
• Gestion de projet : le chemin de valeur maximale du graphe des tâches donne la durée du projet.

Exercices

Exercice 1 sur 4 Longueur et valeur Réussi À revoir

On reprend le graphe valué du cours.

1. Donne la longueur et la valeur du chemin (A, B, D, E, F).
2. Combien de chemins de A vers F ont la longueur 4 ? Donne-les avec leur valeur.
3. Le sous-chemin (B, D, E, F) du chemin minimal est-il un chemin minimal de B vers F ? Vérifie-le.

Voir la réponseMasquer la réponse de l'exercice 1

1. Longueur 4 (quatre arcs), valeur 4 + 5 + 2 + 2 = 13.
2. Trois chemins : (A, B, D, E, F), valeur 13 ; (A, C, B, D, F), valeur 2 + 1 + 5 + 6 = 14 ; (A, C, D, E, F), valeur 2 + 8 + 2 + 2 = 14.
3. Depuis B, le seul successeur est D ; depuis D, on va en F directement (6) ou par E (2 + 2 = 4). Les chemins de B vers F valent donc 5 + 6 = 11 et 5 + 4 = 9 : le minimum est 9, atteint par (B, D, E, F). Oui, conformément au principe d'optimalité.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 4 Chemin minimal et chemin maximal par niveaux Réussi À revoir

Un graphe valué sans circuit a pour arcs : A → B (3), A → C (6), B → C (2), B → D (7), C → D (3), C → E (4), D → F (2), E → F (5), D → G (6), E → G (1), F → G (3).

1. Détermine les niveaux du graphe.
2. Détermine un chemin de valeur minimale de A vers G et sa valeur.
3. Détermine un chemin de valeur maximale de A vers G et sa valeur.
4. Quelle est la plus petite longueur d'un chemin de A vers G ?

Voir la réponseMasquer la réponse de l'exercice 2

1. N₀ = {A}, N₁ = {B}, N₂ = {C} (C a pour prédécesseurs A et B), N₃ = {D, E}, N₄ = {F}, N₅ = {G}.
2. Marques minimales : A = 0 ; B = 3 ; C = min(0 + 6 ; 3 + 2) = 5 (vient de B) ; D = min(3 + 7 ; 5 + 3) = 8 (de C) ; E = 5 + 4 = 9 (de C) ; F = min(8 + 2 ; 9 + 5) = 10 (de D) ; G = min(8 + 6 ; 9 + 1 ; 10 + 3) = 10 (de E). En remontant : G ← E ← C ← B ← A. Chemin minimal (A, B, C, E, G), valeur 10.
3. Marques maximales : A = 0 ; B = 3 ; C = max(6 ; 5) = 6 (de A) ; D = max(3 + 7 ; 6 + 3) = 10 (de B) ; E = 6 + 4 = 10 (de C) ; F = max(10 + 2 ; 10 + 5) = 15 (de E) ; G = max(10 + 6 ; 10 + 1 ; 15 + 3) = 18 (de F). En remontant : G ← F ← E ← C ← A. Chemin maximal (A, C, E, F, G), valeur 18.
4. En couches : A (0) ; B, C (1) ; D, E (2) ; F, G (3). La plus petite longueur est 3, par exemple (A, C, E, G) ou (A, B, D, G).

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 4 RIP ou OSPF ? Réussi À revoir

Cinq routeurs A, B, C, D, E sont reliés par des liens dans les deux sens. Les liens A–B et B–E sont lents (coût 10 chacun), les liens A–C, C–D et D–E sont rapides (coût 1 chacun).

1. Quelle route RIP choisit-il de A vers E (critère : nombre de sauts) ?
2. Quelle route OSPF choisit-il (critère : coût total) ?
3. Explique pourquoi le principe d'optimalité garantit que la route OSPF de A vers D est (A, C, D).

Voir la réponseMasquer la réponse de l'exercice 3

1. Les routes de A vers E sont (A, B, E), 2 sauts, et (A, C, D, E), 3 sauts. RIP choisit (A, B, E), la plus courte en longueur.
2. Coûts : (A, B, E) vaut 10 + 10 = 20, (A, C, D, E) vaut 1 + 1 + 1 = 3. OSPF choisit (A, C, D, E), optimale en valeur.
3. (A, C, D) est un sous-chemin du chemin optimal (A, C, D, E) : il est donc lui-même optimal de A vers D. (Les autres routes de A vers D passent par B et coûtent au moins 10 + 10 + 1 = 21.)

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 4 Vrai ou faux Réussi À revoir

1. Dans un graphe valué, le chemin optimal en longueur est toujours optimal en valeur.
2. Si (A, B, C, D) est un chemin minimal de A vers D, alors (B, C) est un chemin minimal de B vers C.
3. Dans un graphe dont tous les arcs ont la valeur 1, longueur et valeur d'un chemin sont égales.
4. On peut toujours chercher un chemin de valeur maximale, même dans un graphe qui a des circuits.

Voir la réponseMasquer la réponse de l'exercice 4

1. Faux : dans le graphe du cours, le chemin minimal de A vers F a 5 arcs alors que la plus petite longueur est 3.
2. Vrai : c'est le principe d'optimalité, (B, C) est un sous-chemin d'un chemin optimal.
3. Vrai : la valeur est la somme de p fois 1, soit p, la longueur.
4. Faux : avec un circuit de valeur positive, on augmente la valeur sans limite en tournant dans le circuit. Le problème n'a de sens que pour des chemins sans circuit.

Tu avais trouvé ?

Oui, j'avais bonPas encore