Chapitre : Graphes étiqueté et orienté

Illustration

(voir fiche)

Définition d’un graphe étiqueté

Un graphe orienté étiqueté par des nombres est un triplet (S,A,f) avec :

• S un ensemble fini appelé l’ensemble des sommets.
• A : un ensemble fini appelé l’ensemble des arcs.
• f : une application de A dans $S \times S \times \mathbb{R}$ (produit cartésien).

$f :A \rightarrow S \times S \times \mathbb{R}$

Exemple

S : { a,b,c,d,e,f}

A : {$\alpha,\beta,\gamma, S,n$}

(voir fiche)

Implémentation

• liste d'adjacences

a : (b,3)
b :
c : (c,6)
d : 
e : 
f : (e,-2)
g : (f,1),(f,3)

• on peut utiliser une matrice d'adjacences

(voir fiche)

Problèmes :

• pas d'arc
• plusieurs arcs

Solutions ?

• chaque case représente un ensemble
• une valeur distinguéereprésente l'absence d'arc

Longueur d'un chemin (définition)

Soit un chemin d'un graphe étiqueté $(S,A,f)$

$v,a_0,a_1,a_2,a_3...,a_k$

avec $v \in S, \forall i \in \mathbb{N}, i \leq k, a_i \in A$

et tel que $\forall i\in \mathbb{N}, i < k,$

$f(a_i) = (o,d,e)$

$f(a_{i+1})= (d,n,k)$

La longueur du chemin est la somme des étiquettes des arcs du chemin, c'est à dire :

$e_0 + e_1 + ... + e_k$ avec $\forall i \in \mathbb{N}, i \leq k$

$f(a_i) = f(...,...,e_i)$

Par convention, la longueur d'un chemin trivial (qui n'emprunte aucun arc) est 0.

Distance d'un sommet à un autre (définition)

Soit G un graphe étiqueté, soit a,b deux sommets

• On appelle distance de a à b, la borne inférieure de l'ensemble des longueurs des chemins partants de a et aboutissants à b.

• notée (a,b)

• d(a,b) := inf {longueur(c) : c chemin de a à b}

Illustration

(voir fiche)

Il faut choisir le plus court

• $d(a,c) = 4$
• $d(c,a) = + \infin$
• $d(u,h) = - \infin$

Algorithme de Dijkstra

Entrée :

• G un graphe orinté étiqueté par des nombre réels positifs non nul.
• s : un sommet

Sortie :

• Pour chaque sommet v de G, la distance de s à v (et si cette distance $\neq + \infin$ un chemin qui la réalise).

Illustration :

(voir fiche)

Au départ, chaque sommet possède une distance hypothétique de $+ \infin$ sauf le sommet de départ qui possède une distance de 0.

A chaque étape on fait grandir un ensemble D de sommet vide au départ

1. on ajoute à D un sommet qui n'appartient pas à D et dont la distance hypothétique est la plus petite
2. Pour tous succésseur direct du sommet V on met à jour sa distance hypothétique.

Lorque D contient tous les sommets, on a les distances vraies.