This note describes a generalization of an algorithm given by Aho, Hopcroft, and Ullman , originally derived from the work of Kleene  and McNaughton and Yamada . 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-1E[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.
The full text of this article is premium content
No entries found
Log in to Read the Full Article
Purchase the Article
Create a Web Account
If you are an ACM member, Communications subscriber, Digital Library subscriber, or use your institution's subscription, please set up a web account to access premium content and site
features. If you are a SIG member or member of the general public, you may set up a web account to comment on free articles and sign up for email alerts.