Algorithme global de cheminement sur la représentation matricielle
Problématique des problèmes de cheminement considérés
On s'intéresse ici à la troisième famille des problèmes de cheminement, pour lesquels on souhaite connaître la valeur des chemins extrémaux de tout point x à tout point y.
Par contre, l'algorithme ne fournit pas les chemins correspondant.
Définition des opérations matricielles liées aux chemins extrémaux
Cet algorithme fait partie des algorithmes dits globaux.
Ils peuvent résoudre des problèmes de recherche de chemins minimaux ou maximaux ou les plus probables ou encore d'existence de chemin.
Pour les présenter, on utilise deux opérateurs : un opérateur || et un opérateur &.
Les deux opérateurs sont commutatifs et ω est l'élément neutre de ||.
Pour les problèmes de chemins minimaux : || = Min, & = + et ω = + ∞ ;
Pour les problèmes de chemins maximaux : || = Max, & = + et ω = - ∞ ;
Pour les problèmes d'existence de chemins : || = OU, & = ET et ω = faux ;
Pour les chemins les plus probables : || = max, & = * et ω = 0 ;
Structure de données utilisées pour l'algorithme de Roy-Warshall
La matrice V donne la longueur des arcs du graphe.
V(i,j) est égale à +∞ quand l'arc (i,j) n'existe pas.
Deux matrices carrées RW0 et RW1 de n lignes et n colonnes, où n est le nombre de points du graphe, sont utilisées par l'algorithme.
Description de l'algorithme de Roy-Warshall sous sa forme globale
Initialisation :
RW0 = V ;
Pour k de 1 à n faire
Une itération
Pour i de 1 à n faire
Pour j de 1 à n faire
RW1 (i, j) = (RW0 (i, k) & RW0 (k, j) || RW0 (i, j) ;
Fin Pour j ;
Fin Pour i ;
RW0=RW1 ;
Fin Pour k ;
Description de l'algorithme de Roy-Warshall pour la recherche de longeurs de chemins minimaux
Initialisation :
RW0 = V ;
Pour k de 1 à n faire
Une itération
Pour i de 1 à n faire
Pour j de 1 à n faire
RW1 (i, j) =Min (RW0 (i, k) + RW0 (k, j) , RW0 (i, j) ) ;
Fin Pour j ;
Fin Pour i ;
RW0=RW1 ;
Fin Pour k ;
Convergence et complexité
Le nombre de calculs effectué par cet algorithme est proportionnel à n3.
On est donc certain qu'il converge.
Les circuits de longueurs strictement négatives pour un minimum ou strictement positives pour un maximum, ne sont pas utilisés de manière itérative par l'algorithme.
Néanmoins, pour que les plus courts chemins aient un sens lorsqu'il existe des circuits, on supposera qu'il n'existe pas de circuit de longueur strictement négatives pour un minimum ou strictement positives pour un maximum.
Éléments de preuve de l'algorithme
Initialisation
En début d'algorithme, la matrice RW0 contient la longueur la plus courte des chemins en un seul arc avec 0 point intermédiaire de tout point i à tout point j.
Hypothèse de récurrence
A la fin de l'itération k, RW0 contient la longueur des plus courts chemins allant de tout point i à tout point j et passant éventuellement par un sous-ensemble de points intermédiaires, ce sont les points numérotés de 1 à k.
Démonstration de la récurrence
L'hypothèse est vérifiée à l'initialisation.
On suppose que l'hypothèse est vérifiée à la fin de l'itération k-1, et on considère l'itération k.
Pour trouver les plus courts chemins de i à j passant par 1, 2, ... , k. On peut séparer ces chemins en deux sous-ensembles, ceux qui passent par le point k et ceux qui ne passent pas par le point k.
Pour ceux qui ne passent pas par le point k, la longueur du plus court chemin se trouve dans RW0 par hypothèse de récurrence.
Pour ceux qui passent par le point k. Il ne passe qu'une seule fois par le point k (puisque les circuits sont supposés ne pas avoir une longueur strictement négative). Ils sont donc constituer de deux parties, une partie de i à k qui ne passe que par des points 1, 2, ..., k-1 dont on peut trouver la longueur du chemin le plus court dans RW0 et une partie de k à j qui ne passe que par des points 1, 2, ..., k-1 dont on peut trouver la longueur du chemin le plus court dans RW0. La longueur du chemin le plus court de i à j passant par k est égale à la somme de ces deux chemins. Et le plus court chemin est obtenu en prenant le plus court des plus courts chemins ne passant pas par k et passant par k.
Déroulement de l'algorithme sur un premier exemple
Il y a un seul graphe où tous les arcs existant sont de longueur 1.
En conséquence, le résultat final de l'algorithme donne le chemin minimal en nombre d'arcs entre tout couple de points.
Le bouton PLUS permet de dérouler l'algorithme en pas à pas.
Le bouton RAZ permet de recommencer l'algorithme au début si vous le souhaitez.
Les petits graphes en dessous des tableaux permettent de voir les arcs ou les chemins qui existent, mais les longueur des chemins minimaux trouvés doivent être examinés sur les matrices RW0 et RW1.
Pour des raisons de lisibilité, les valeurs infinies ont été notées par # dans les matrices (elles dénotent l'absence de chemins entre i et j).
Le résultat est dans la dernière matrice à droite lorsque le mot FIN apparaît après étude du dernier point.
Déroulement de l'algorithme sur un deuxième exemple
Le fonctionnement est le même que pour l'exemple précédent.
Pour ce deuxième exemple, des valeurs souvent différentes ont été attribuées aux arcs qui existent.
