Note that in practice, for numerical stability, all of these computations are done in the log semiring which is isomorphic to (R + ∪ {+∞}, +, ×, 0, 1).
the maximum weight path in the last step is then obtained by using a standard single-source shortest-path algorithm.