Max-plus algebra

Summary

Max-plus algebra is linear algebra in which addition is replaced by taking the maximum and multiplication is replaced by ordinary addition. These operations make $\R \cup \set{-\infty}$ a semiring, the max-plus semiring. It is one form of the tropical semiring. Matrices over it describe longest paths in weighted graphs. They also model the timing of systems that wait for several events, such as train schedules.