Base des données orientées-graphe: migration du relationnel vers le noSQL

I.2.7. Graphe pondéré - Réseau - Réseau de transport

a. Graphe pondéré

Soit G = (X, U) :

· On dit que G est pondéré à tout arc (x_i, x_j) U, si on associe le nombre c_ij R ;

· La matrice C=(c_ij) _{(i, j) U} est appelé matrice de pondération.

· On note alors le triplet G=(X, U, C) le graphe pondéré.

A savoir que la pondération ou la valeur c (x_i, x_j) est une valeur résultant d'une mesure. Cette mesure peut être :

· Une distance du sommet x_i au sommet x_j ;

· Un coût sur l'arc (x_i, x_j) ;

· Une pénalité, par exemple : Paiement associé à l'arc (x_i, x_j) ;

· Une probabilité de transition du sommet x_i au sommet x_j ;

· Une durée (temps) entre x_i et x_j ;

· Une consommation (de carburant, etc.) à effectuer du x_i au sommet x_j ;

· Etc.

Exemple 1.14 : Soit le graphe G=(X, U, C).

Le graphe ci-contre est pondéré dans la mesure où, de chaque, on a associé une valeur numérique quelconque.

a

-5

c

5

19

e

13

d

2

3

b

1

1

g

-2

3

f

9

2

Figure 1.14 : Illustration d'un graphe pondéré

b. Réseau

Un réseau est un graphe pondéré sans boucle. Pour ce faire, on note

R=(X, U,?) un graphe pondéré sans boucle ni circuit à valeur négative.

c. Réseau de transport

(i) R=(X, U,?) est un réseau de transport si et seulement si c'est un graphe pondéré sans boucle ni circuit à valeur négative et c (x_i,x_j) = 0, (x_i,x_j) U.

(ii) R=(X, U,?) est un réseau de transport si et seulement si c'est un graphe pondéré sans boucle ni circuit à valeur négative et c (x_i,x_j) = 0, x_i,x_j X.

NOTA : La définition (i) et (ii) sont équivalentes ;

I.2.8. Problème de Cheminement optimale

a. Valeur d'un chemin

Soit G=(X,U) un graphe. Si à chaque arc (x_i,x_j) U, on associe le nombre le nombre c_ij R*, tel que c_ij = valeur (x_i,x_j) = c (x_i,x_j).

Considérons la loi de composition interne binaire + dans R*. On appelle valeur d'un chemin (x_i1, x_i2, ..., x_ik), le nombre noté « l », tel que :

l = c_i1, c_i2 + c_i2, c_i3 + ... + c_{ik - 1}, c_ik

Exemple 1.15 : Considérons le graphe suivant :

b

a

c

e

f

d

z

5

2

10

30

40

90

100

6

11

8

7

11

Figure 1.15 : Graphe pondéré

On a : c_ab=c(a,b)=5 ; c_bd=c(b,d)=8 ; c_dc=c(d,c)=4 ; c_ce=c(c,e)=3

l (a, b, d, c, e) = 20  

Remarque 

S'il existe un chemin qui correspond à la plus grande (ou petite) valeur de l, on l'appelle « plus long (ou court) chemin » du graphe.

b. Types d'algorithmes de cheminement optimal

Il existe deux types de cheminement optimal, se basant toutes sur le principe d'optimalité de Richards Bellman. On cite :

· Les algorithmes constructeurs d'arbre (Tree builder) qui consistent à construire l'arbre à valeur optimale entre la racine (source) et les autres noeuds du réseau ;

· Les algorithmes matriciels qui consistent à trouver le chemin à valeur optimale entre tous les couples de sommet (x_i,x_j) U.

Dans ce travail, on s'intéressera qu'à un algorithme Tree builder de plus court chemin, appelé Algorithme de Dijkstra, car c'est cet algorithme qui est utilisé dans l'implémentation des bases de données orientées-graphe.

c. Algorithme de Dijkstra (pour le plus court chemin)

c.1. Origine

Cet algorithme est dû aux recherches de l'Informaticien et Mathématicien néerlandais (alors qu'il était diplômé en Physique théorique, mais trop intéressé à l'Informatique notamment le Système d'exploitation et les principes de programmation) appelé Edsger Dijkstra. Cet algorithme fut publié en 1959.

Cet algorithme est plus utilisé dans le calcul des itinéraires routiers. Une autre application les plus courantes de cet algorithme est le protocole Open Shortest Path Fist (OSPF) qui est utilisé pour le routage internet ; il permet des informations. Les routeurs tels que IS-IS sont implémentés en algorithme de Dijkstra. [Wiki1]

c.2. Principe

L'algorithme de Dijkstra s'appuie directement sur le principe d'optimalité de Richards Bellman selon lequel : « dans un graphe, tout chemin optimal comprenant au plus r arcs est formé des sous-chemins contenant au plus k arcs (k=r) et qui sont eux aussi optimaux entre leurs sommets extrémités ».

Algorithme 1.1

1. (Numérotation)

Numéroter les sommets du graphe dans un ordre quelconque, en observant toutefois que le sommet de départ doit être marqué x₀ et celui d'arrivé x_n-1 si n est le nombre total de sommets du graphe.

2. (Initialisation)

Pour tout sommet x_i (i?0)

On affecte provisoirement à tous les x_i une étiquette de poids (x_i)

une valeur 8, c'est-à-dire :

poids (x_i) 8

Fin pour

3. poids (x₀) 0

4. S X

5. Tant que ð?S

Choisir un sommet x_j ð / poids (x_j) = poids (x_j)

ð ð { x_j }

Pour tout voisin x_j de x_i de ð

Sipoids (x_j) + v (x_i,x_j) < poids (x_j) Alors

Mémoriser en x_j que l'on vient de x_i

Fin si

Fin pour

Fin tant que

6. Fin