A more general algorithm for computing closed semiring costs between vertices of a directed graph

This note describes a generalization of an algorithm given by Aho, Hopcroft, and Ullman [1], originally derived from the work of Kleene [2] and McNaughton and Yamada [3]. The algorithm is used to compute the total cost of all paths between each pair of vertices in a directed graph when the cost of each edge is known. The cost of a path is defined as the product of the costs of the edges forming it, and the total cost of a set of paths is the sum of their individual costs. If there are n vertices labeled 1 through n and E[i, j] is the cost of the edge from vertex i to vertex j (or is zero when there is no such edge), then the total cost T[i, j] of all paths from i to j is the solution of the equation T[i, j] = &dgr;[i, j] + ∑nk-1 E[i, k]·T[k, j], (1) where &dgr;[i, i] = 1 (the cost of the path of no edges from i to i) and &dgr;[i, j] = 0 if i ≠ j. To assure that T [i, j] is always well-defined, costs are required to be elements from an algebraic structure called a closed semiring.

View this article in the ACM Digital Library.