After formal language theory, shortest-distance problems are the area in which semirings have been used most efficiently to solve problems of direct interest to computer scientists.

This paper presents a unified semiring-based framework for single-source shortest-distance problems, including a generic algorithm for solving such problems. Included is a proof of the correctness and termination of the algorithm, as well as a complete analysis of its running-time complexity, with respect to the times for computing the operations in the underlying semiring. At the end of the paper, a framework and genetic algorithm for computing all-pairs shortest-distances are presented.

The paper is a good bridge between the considerable theoretical work being done by mathematicians, and the needs of the working software designer. Unfortunately, however, the bibliography is rather brief, and makes no mention of many important works in the area, especially those published in French and Russian.