A general method is described for solving path problems on directed graphs. Such path problems include finding shortest paths, solving sparse systems of hnear equaUons, and carrying out global flow analysis of computer programs The method consists of two steps First, a collecUon of regular expressions representmg sets of paths m the graph Is constructed This can be done by using any standard algorithm, such as Gaussmn or Gauss-Jordan elimination. Next, a natural mapping from regular expressions into the gwen problem domain is applied. The mappmgs required to find shortest paths are exhibited, sparse systems of hnear equations are solved, and global flow analysis Is carned out. The results provide a general-purpose algonthm for solwng any path problem and show that the problem of constructing path expressions is in some sense the most general path problem.
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence