Graphs, Dioids and Semirings New Models and Algorithms

During the last two or three centuries, most of the developments in science (in p- ticularinPhysicsandAppliedMathematics)havebeenfoundedontheuseofclassical algebraic structures, namely groups, rings and ?elds. However many situations can be found for which those usual algebraic structures do not necessarily provide the most appropriate tools for modeling and problem solving. The case of arithmetic provides a typical example: the set of nonnegative integers endowed with ordinary addition and multiplication does not enjoy the properties of a ?eld, nor even those of a ring. AmoreinvolvedexampleconcernsHamilton–JacobiequationsinPhysics,which may be interpreted as optimality conditions associated with a variational principle (forinstance,theFermatprincipleinOptics,the‘MinimumAction’principleofM- pertuis,etc.).Thediscretizedversionofthistypeofvariationalproblemscorresponds tothewell-knownshortestpathprobleminagraph.ByusingBellmann’soptimality principle, the equations which de?ne a solution to the shortest path problem, which are nonlinear in usual algebra, may be written as a linear system in the algebraic structure(R?{+?},Min,+), i.e. the set of reals endowed with the operation Min (minimum of two numbers) in place of addition, and the operation+ (sum of two numbers) in place of multiplication. Such an algebraic structure has properties quite different from those of the ?eld of real numbers. Indeed, since the elements of E= R?{+?} do not have inverses for?= Min,thisinternaloperationdoesnotinducethestructureofagrouponE.In that respect (E,?,?) will have to be considered as an example of a more primitive algebraic structure as compared with ?elds, or even rings, and will be referred to as a semiring. Butthisexampleisalsorepresentativeofaparticularclassofsemirings,forwhich the monoid (E,?)is ordered by the order relation? (referred to as ‘canonical’) de?ned as: a? b?? c? E such that b= a? c.