A Unified Approach to Path Problems

Research output: Contribution to journalArticlepeer-review

176 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)577-593
Number of pages17
JournalJournal of the ACM (JACM)
Issue number3
StatePublished - Jul 1 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence
  • Information Systems
  • Control and Systems Engineering
  • Hardware and Architecture


  • Ganss-Jordan ehmmatlon
  • Gaussian elmamation
  • code optimization
  • compiling
  • global flow analysis
  • graph algorithm
  • linear algebra
  • path problem
  • regular expression
  • semdattlce
  • shortest path
  • sparse matrix


Dive into the research topics of 'A Unified Approach to Path Problems'. Together they form a unique fingerprint.

Cite this