Algèbre min-plus

Algèbre max-plus

Une algèbre max-plus est une algèbre sur les nombres réels munie des opération de maximum et d'addition.

Ainsi si on note $\oplus$ l'opération maximum et $\otimes$ l'addition, les opérations sont définies par:

$A \bigoplus B = max(A,B)$
$A \bigotimes B := A + B$

On peut alors vérifier que ces opération sur les réels vérifient bien celles exigé par la structure d'algèbre.

Cette algèbre est liée à l'algèbre des dioïdes

Application au calcul distances dans un graphe pour l'algèbre min-plus

On se place ici dans l'algèbre min-plus (l'opération max est remplacé par l'opération min).

On peut représenter un graphe à n sommets comme une matrice A = (a_i,j) des distances entre chaque sommet: si le sommet i et lié avec le sommet j alors l'élément a_i,j est égale au poids de l'arrête (i,j), si les sommets i et j ne sont pas reliées alors a_i,j correspond à l'infini (on a a_i,i = 0).

Ainsi la distance entre i et j en passant par au plus un sommet est: min_kestunsommet(a_i,k + a_k,j)

Ceci correspond au produit matriciel dans l'algèbre min-plus. Ainsi pour calculer la longueur d'un plus court chemin d'un sommet à un autre dans le graphe il suffit de calculer la puissance n de A dans cette algèbre.

Ce document provient de « Alg%C3%A8bre max-plus ».