摘要
给出了有向图中求解源结点到各顶点之间所有路径问题的一个算法,该算法能够求出他们的所有路径,并按照路径权值的大小递增排列.在算法的实现中第一次应用邻接矩阵求解各结点的前趋以便得到各结点的路径运算顺序,然后通过邻接表的数据结构实现此算法.此算法已用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.
出处
《微电子学与计算机》
CSCD
北大核心
2009年第3期128-130,共3页
Microelectronics & Computer
基金
江西省自然科学基金项目(0611092)
关键词
有向图
前趋结点
权
邻接矩阵
diagraph
predecessor node
weight
adjacency list
