拓扑排序法的修正算法

梁娟¹

扫码查看

作者信息

1. 无锡太湖学院,江苏无锡 214064
折叠

摘要

拓扑排序法是求解无回路网络中最短路径的经典算法之一,该算法在计算最短路径的权值时,每次都要计算临时标号集合中所有节点的值.另外,拓扑排序法用两个值标记一个节点,在寻找最短路径时比较繁琐.本文提出的拓扑排序法的修正算法用三个值标记一个节点,前点标号的增加使得寻找最短路径更加容易,修正算法还通过只计算与节点的出弧相连的临时节点的值,从而达到简化计算的目的.最后通过具体实例分析表明,拓扑排序法的修正算法改善了寻找最短路径繁琐的问题,减少了重复计算,提高了计算效率.

关键词

拓扑排序法/修正算法/无回路网络/最短路径

引用本文复制引用

出版年

2017

科技展望

宁夏科技信息研究所

科技展望

ISSN：1672-8289

参考文献量2

段落导航