摘要
有向图的路径问题有广泛的应用,其中求最短路问题有经典的算法,K短路问题也有很多研究,但求所有可达路径的算法却见之甚少。本文提出一种有向图无负权所有可达路径搜索算法,并对该算法的时间、空间复杂性作了分析。
Directed graph routing problem has extensive application, in which an algorithm of solving shortest path is classic. K-shortest path algorithm has widely been studied, but algorithm for selecting all feasible paths is very limited. This paper gives a search algorithm of all feasible paths for directed graph without negative weights and discusses the complexity of both time and space of the algorithm.
出处
《长春大学学报》
2009年第2期57-59,共3页
Journal of Changchun University
基金
吉林省教育厅科研项目(吉教科文合字[2006]36号)
关键词
最短路径
全路径
算法
shortest path, all paths, algorithm
