Quelle est la différence entre la longueur et le coût d’un chemin dans un graphe pondéré ?

Réponse courte

La longueur d’un chemin est le nombre d’arêtes ou d’arcs qu’il parcourt. Son coût est la somme des poids associés à ces liaisons. Un chemin peut donc être plus court en nombre d’étapes sans être le moins coûteux.

Comprendre

Deux mesures distinctes

La longueur compte les liaisons traversées, sans tenir compte de leur poids. Dans un graphe pondéré, chaque liaison porte une valeur qui modélise par exemple une durée, une distance ou un prix. Le coût d’un chemin est la somme de ces poids. On compare les coûts dans une même unité et selon le sens donné aux poids par le modèle.

Exemple avec des durées

Supposons trois lieux A, B et C, avec A vers C de poids 8 minutes, A vers B de poids 2 minutes et B vers C de poids 3 minutes. Le chemin direct A vers C a une longueur de 1 et un coût de 8 minutes. Le chemin A, B, C a une longueur de 2 et un coût de 2 + 3 = 5 minutes. Il comporte davantage d’arcs, mais son coût est inférieur.

Bien lire la question

Si l’on cherche le chemin de longueur minimale, on minimise le nombre de liaisons. Si l’on cherche le chemin de coût minimal, on additionne les poids puis on compare les sommes. Ces objectifs ne coïncident pas forcément ; il faut donc identifier la grandeur demandée avant de choisir un trajet.

Exemples

  • A→C pèse 8 min : longueur 1, coût 8 min. A→B→C pèse 2 min puis 3 min : longueur 2, coût 5 min.
  • Un trajet de 3 arcs de poids 1, 1 et 4 a longueur 3 et coût 6 ; un arc unique de poids 7 a longueur 1 et coût 7.

Pièges fréquents

  • Appeler « coût » le nombre d’arêtes : c’est la longueur ; le coût additionne les poids portés par les arêtes ou arcs.
  • Comparer directement un nombre d’arcs à une durée en minutes : ce sont des grandeurs différentes, dont l’objectif doit être précisé.

Et maintenant ?

Questions proches

← Toutes les questions-réponses