求有向图中源点到各结点所有路径的一种实用算法  

An Algorithm for Finding all Paths Between Source Node and other Nodes in a Digraph

作　　者：毛红梅[1] 甘晟科[1] 

机构地区：[1]南昌航空大学计算机学院,江西南昌330063

出　　处：《微电子学与计算机》2009年第3期128-130,共3页Microelectronics & Computer

基　　金：江西省自然科学基金项目(0611092)

摘　　要：给出了有向图中求解源结点到各顶点之间所有路径问题的一个算法,该算法能够求出他们的所有路径,并按照路径权值的大小递增排列.在算法的实现中第一次应用邻接矩阵求解各结点的前趋以便得到各结点的路径运算顺序,然后通过邻接表的数据结构实现此算法.此算法已用C语言编制的相应程序验证了其可靠性和实用性.In this article,an algorithm for finding all paths between source node and other nodes in a digraph is put forward.The algorithm can obtain all the paths,as same as an array of ordered paths to weight.Predecessor nodes were applied at first to obtain other node s calculated sequence,and adjacency list data structure was applied in this algorithm.In this article,some instances are provided to prove the algorithm reliable and useful.

关 键 词：有向图 前趋结点 权 邻接矩阵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]