Journal of the ACM · 1981 · 251 citations · 24 references
BusinessInformation SystemsDecision Support SystemsPath PlanningPlanning TheoryCitation NetworksCitation Practices
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.
24
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Patrick Cousot, Radhia Cousot · 1977 · 6.2K citations
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
Gaussian elimination is not optimal
Volker Strassen · Numerische Mathematik · 1969 · 2.5K citations
Stephen Warshall · Journal of the ACM · 1962 · 1.7K citations