Meilleurs chemins issus d’un sommet s donné

Chemins et circuits, chaînes et cycles

Un chemin dans un graphe orienté est une suite d’arcs. L’origine d’un arc étant l’extrémité de l’arc précédent. Un chemin est dit simple s’il ne passe pas deux fois par le même arc. Il est élémentaire si tous ses sommets sont différents. Un circuit est un chemin dont l’origine et l’extrémité sont confondues. Dans le cas d’un graphe non orienté, par exemple G°, nous parlerons de chaîne et de cycle qui correspondent respectivement au chemin et au circuit du graphe G admettant pour graphe non orienté sous-jacent, ce graphe G°.

Connexité

Connexité d’un graphe non orienté

Soit un graphe non orienté G <S, A>, la relation R sur l’ensemble S définie par : ∀x ∈ S,∀y ∈ S , R(x, y) : «il existe une chaîne entre x et y ou bien x = y » est une relation d’équivalence qui partitionne S en classes d’équivalence. Un graphe est connexe s’il ne comporte qu’une seule classe d’équivalence engendrée par cette relation. En d’autres termes un graphe est connexe s’il existe une chaîne entre deux sommets quelconques de ce graphe. Ces classes d’équivalence constituent les composantes connexes des éléments y appartenant.

Forte connexité d’un graphe orienté

Soit maintenant la relation R’ définie sur les éléments de S dans un graphe orienté : ∀x ∈ S,∀y ∈ S , R(x, y): «il existe un chemin reliant x à y ou bien x = y».Un
graphe est dit fortement connexe, s’il ne comporte qu’une seule classe d’équivalence.

Arbres et Arborescences

Un arbre est un graphe simple non orienté connexe et sans circuit. Cette définition fait que, pour deux sommets quelconques, il n’y a qu’une seule chaîne les reliant. En plus nous avons |A| = |S| -1. Une arborescence est un graphe orienté possédant un sommet particulier ; la racine. Il existe qu’un et un seul chemin de la racine vers tout autre sommet. La racine n’a pas de précédent. Un arbre peut être orienté à partir de tout sommet pour donner une arborescence. Nous utiliserons le terme arbre pour désigner aussi bien une arborescence qu’un arbre au sens strict (non orienté).
Fig. 5 : Arbre et arborescence.

Représentation en informatique des graphes

La représentation des graphes est très importante pour la résolution de problèmes modélisés par ces derniers. En effet, l’algorithme doit beaucoup s’appuyer sur cette représentation pour prendre en compte les contraintes spatiales et temporelles. Aussi faut il, en élaborant l’algorithme, avoir en tête l’amélioration de sa complexité suivant telle ou telle autre structure de représentation.

Représentations matricielles

Matrice d’incidence sommet – sommet

Cette représentation ne concerne que les graphes simples et se base sur le principe suivant : A tout graphe G<S, A> est associé une matrice carrée M (|S|, |S|). Il convient alors de numéroter les sommets du graphe de 1 à |S|.
Un graphe non orienté admettra donc une matrice symétrique. Voyons maintenant les avantages et les inconvénients d’une telle représentation.
Avantages :
– la représentation est très compacte simplifiant les algorithmes qui s’y appliquent.
– la détection d’un arc est aussi très rapide.
– redondance de l’information pour un graphe non orienté.
– il est impossible de représenter un multigraphe.
– les zéros de la matrice sont stockés inutilement.
Avantages :
– représentation très compacte
– la détection d’un arc est aussi très rapide.
– possibilité de représentation d’un multigraphe Inconvénients :
– stockage inutile des zéros de la matrice
– très difficile d’appliquer les calculs classiques des matrices.

Représentation par listes d’adjacence

Plus proche de la représentation graphique, elle consiste à donner pour chaque sommet x, Γ x . Cet ensemble sera donné sous forme d’une liste chaînée. Notons que les éléments des listes sont donnés dans un ordre quelconque. Il y a en tout |S| listes constituées ensemble de |A| éléments.
Avantages :
– résout le stockage des zéros des matrices précédentes
– facilite la mise à jour et le parcours
– permet l’ajout de variantes au graphe, par exemple le poids des arcs (au lieu de donner le suivant, on peut enregistrer l’arc sortant correspondant) que nous
verrons dans la suite
Inconvénients :
– pour vérifier l’existence d’un arc, il faut procéder à une recherche dans une liste chaînée
– redondance pour les graphes non orienté
– temps d’accès aux données

Représentation par l’ensemble des arcs

Il s’agira tout simplement de donner pour chaque arc son origine et son extrémité.
Avantages :
– résout le stockage des zéros des matrices précédentes
– facilite le parcours des arcs
– permet l’ajout de variantes aux arcs
– complexifie les algorithmes classiques sur les graphes

Formulation

Etant donné un graphe simple orienté G <S, A> où à chaque arc (i, j) est associé une valeur a ij ∈ R . Cette valeur peut représenter dans la pratique, une distance, un
coût, une pénalité, une probabilité, où même le temps de parcours entre les deux nœuds i et j ; nous parlerons dans notre étude de poids. Le graphe G <S, A> alors pondéré est doté de la fonction p définie de la manière suivante : p: A → R a = (i, j) → p(a) = a ij
Un chemin dans le graphe G <S, A, p> aura pour poids la somme des poids de ses arcs. Le problème du plus court chemin est de trouver entre deux nœuds quelconques ou donnés, le chemin de poids minimal. Dans la suite, nous confondrons chemin de poids minimal et plus court chemin.
Circuit absorbant : Il est très important de rappeler la notion de circuit absorbant qui est, dans la recherche de plus courts chemins, un circuit de poids négatif. Un graphe comportant un tel circuit n’admet pas de solution du fait que ce circuit améliore infiniment le chemin optimal recherché. D’où l’intérêt porté aux valeurs des poids et à la présence de circuit absorbant.
Certains algorithmes, comme celui de Floyd-Wharshall ou de Johnson, donnent le meilleur chemin entre deux sommets quelconques, tandis que d’autres se limitent à trouver les chemins d’un sommet donné, à tout autre sommet du graphe : c’est la cas, par exemple, des algorithmes de Ford-Bellman et de Dijkstra.
Pour ce dernier cas, différentes démarches seront adoptées suivant que :
– les valeurs a ij sont réelles mais G n’a pas de circuit absorbant (Ford-Bellman)
– les valeurs a ij sont positives (Dijkstra)
– les valeurs a ij sont réelles mais G est acyclique.
La valeur + ∞ dans le problème de recherche du plus court chemin est « éliminatoire », elle résout donc l’absence de cet arc. Remarquons que la matrice M est semblable à la matrice d’incidence sommet – sommet du graphe ; le 1 pour signifier l’existence d’un arc est simplement remplacé par le poids de cet arc. Pour chaque nœud i du graphe nous allons voir, pour tous les autres nœuds pris deux à deux successivement, soient j et k, si en passant par i on peut obtenir un chemin de poids inférieur à celui qui reliait auparavant j à k. Wharshall propose en plus la variante D[i, j] qui représente le poids minimal du chemin de i à j.
Cet algorithme résout le problème des poids minimaux mais ne donne pas les chemins correspondants. Pour déterminer les chemins en question, il faudrait une autre matrice C telle que la valeur C[j,k] représente le sommet i par lequel il faut passer dans un chemin, le plus court, de j à k . Des appels récursifs donneront ensuite les chemins recherchés. Cette procédure, que nous verrons à la fin de cette section, ne fera qu’augmenter le coût de l’algorithme.

Preuve de l’algorithme

Nous allons procéder par récurrence sur i et montrer que après le ième passage, D[j,k] est le poids minimal du chemin reliant j et k, et dont les sommets intermédiaires sont d’indice inférieur à i (soient 0,1,2,…..,i). Avant le début des itérations, il est bien visible que la matrice D contient les valeurs de M. A cette étape ( 0ème passage, si l’on peut dire!), ces poids sont minimaux puisqu’ils représentent les données de départ.