A UNIFIED APPROACH TO PATH PROBLEMS
A UNIFIED APPROACH TO PATH PROBLEMS
复制标题
DOI：
10.1145/322261.322272
复制
发表时间：
1981-01-01
影响因子：
2.5
通讯作者：
TARJAN, RE
中科院分区：
文献类型：
--
作者：
TARJAN, RE
给出了求解有向图上路径问题的一般方法。这类路径问题包括寻找最短路径、求解稀疏的线性方程组和进行计算机程序的全局流分析。该方法包括两个步骤。首先，构造一组表示图中路径集合的正则表达式。这可以通过使用任何标准算法来完成，例如高斯消元法或高斯-约当消元法。接下来，应用从正则表达式到gwen问题域的自然映射。给出了求最短路径所需的映射，求解了稀疏的hnear方程组，并进行了全局流分析。这些结果提供了一个求解任何路径问题的通用算法，并表明构造路径表达式的问题在某种意义上是最一般的路径问题。
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.