Problèmes de plus court chemin

13.6.1 Position du problème et notations

Dans toute la suite, on considère un graphe {G(S,A),} orienté ou non, mais pondéré.

Pour simplifier, on va considérer que la fonction de poids {\varphi} est à valeurs strictement positives. On dispose donc d’une fonction de poids {\varphi :A\times A\to \mathbb{R}^{+\star }\quad :} le poids d’un arc (d’une arête) doit être interprété comme le coût associé au passage par cet arc/arête (par exemple la distance entre deux villes).

Étant donnés deux sommets {i,j} de {G,} on souhaite déterminer la « longueur minimum » de {i} à {j,} c’est-à-dire la somme minimale d’un chemin de {i} à {j:} un chemin réalisant ce minimum sera appelé un « plus court chemin de {i} à {j} ».

Il ne s’agit pas de minimiser le nombre d’étapes de {i} à {j,} mais le poids cumulé de toutes celles-ci : l’expression plus court chemin se comprend mieux quand on imagine que les poids représentent des distances entre sommets.

On étend la fonction poids en donnant la valeur {+\infty} aux arcs/arêtes qui ne figurent pas dans {G(}puisqu’on recherche un chemin de poids minimum, cela revient à écarter toute possibilité, ou tout intérêt, de passer par ces arcs/arêtes).

On représentera le graphe {G(}à {n} sommets) par sa matrice d’adjacence modifiée {M.} Le coefficient {m_{i,j},} au lieu de valoir 1 ou 0 selon que l’arête {\left\{i,j\right\}(}ou l’arc {(i,j))} appartient ou non à {G,} contiendra le poids associé à cet arc/arête.

Par exemple le graphe {G_{3}} ci-dessous sera représenté par la matrice :

Formule du chapitre 13, page 9
{M=}
Figure du chapitre 13, page 9

{\infty}{4} {\infty} {5} {2} {1} {\infty \infty} {G_{3}:} orienté pondéré, de sommets {S=[\![ 0,7]\!]}

Pour travailler sur des exemples de bonne taille, on va utiliser deux fonctions utilitaires :

  • La fonction randpoids, d’argument {n\in \mathbb{N}^{\star}} et {p\in ]0,1[} renvoie la matrice des poids d’un graphe orienté à {n} sommets. Les poids (de type float) sont choisis aléatoirement dans {\left\{1.,2.,...,9.\right\}.} L’argument {p\in ]0,1[} indique une proportion de remplissage (plus {p} est proche de 1 et moins il y a d’arêtes absentes).
  • La fonction convpoids renvoie la conversion d’une matrice de poids en remplaçant les coefficients nuls par infinity, qui est une valeur OCaml de type float et qui joue parfaitement le rôle de la valeur {\infty (}c’est d’ailleurs pour bénéficier de cette facilité qu’on a choisi de représenter les poids par des flottants).

On forme ici une matrice de poids de taille 6 avec un taux de remplissage de 75%, et on y convertit les poids nuls en {\infty :}

Maintenant que nous considérons des poids à valeurs dans {\mathbb{R}^{+\star }\cup \left\{\infty \right\})} on peut considérer que {G} est un graphe complet, c’est-à-dire que tous les sommets sont reliés entre eux (par une arête dans le cas non orienté, et par deux arcs en sens inverses dans le cas orienté), les nouveaux arcs/arêtes ainsi ajoutés (par rapport au graphe original) portant le poids {\infty .}

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :