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 :


{\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 typefloat) 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
convpoidsrenvoie la conversion d’une matrice de poids en remplaçant les coefficients nuls parinfinity, qui est une valeur OCaml de typefloatet 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).
|
1 2 3 4 5 6 7 8 9 |
let randpoids n p = let mp = Array.make_matrix n n 0. in for i = 0 to n-1 do for j = 0 to n-1 do if j != i && Random.float 1. < p then mp.(i).(j) <- float_of_int (1 + Random.int 9) done; done; mp;; (* int -> float -> float array array *) |
|
1 2 3 4 5 6 7 8 9 10 |
let convpoids mp = let n = Array.length mp in let mp' = Array.make_matrix n n infinity in for i = 0 to n-1 do for j = 0 to n-1 do if mp.(i).(j) <> 0. then mp'.(i).(j) <- mp.(i).(j) done; done; mp';; (* float array array -> float array array *) |
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 :}
|
1 2 3 4 5 6 7 8 |
let mp = randpoids 6 0.75;; val mp : float array array = [|[|0.; 5.; 5.; 0.; 0.; 5.|]; [|3.; 0.; 4.; 5.; 2.; 9.|]; [|6.; 9.; 0.; 3.; 5.; 0.|]; [|3.; 9.; 9.; 0.; 0.; 7.|]; [|4.; 0.; 6.; 2.; 0.; 3.|]; [|5.; 4.; 6.; 0.; 9.; 0.|]|] |
|
1 2 3 4 5 6 7 8 |
let mp' = convpoids mp;; val mp' : float array array = [|[|infinity; 5.; 5.; infinity; infinity; 5.|]; [|3.; infinity; 4.; 5.; 2.; 9.|]; [|6.; 9.; infinity; 3.; 5.; infinity|]; [|3.; 9.; 9.; infinity; infinity; 7.|]; [|4.; infinity; 6.; 2.; infinity; 3.|]; [|5.; 4.; 6.; infinity; 9.; infinity|]|] |
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 .}
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres