求图中受顶点数限制的所有最短路径的算法

被引：7

作者：

王卫强

孙强

机构：

[1] 华东师范大学计算机科学技术系

来源：

计算机工程与设计 | 2008年 / 07期

关键词：

逆邻接表; 限制; 最短路径; 生成树; 时间复杂度;

D O I：

10.16208/j.issn1000-7024.2008.07.034

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

提出了图中从一个顶点到另一个顶点的求受顶点数限制的所有最短路径的一个算法,算法基于逆邻接表、最短路径生成树和叶子指针链表等几种特殊的数据结构。对算法进行了详细的理论分析,分析结果表明该算法实现简单、效率较高,且易于描述、实现和理解,并用C语言设计了相应的程序验证了该算法。

引用

页码：1754 / 1757

页数：4

共 8 条

[1] 求带多个限制条件的单源多权最短路径算法 [J].

戴树贵 ;

潘荫荣 ;

胡幼华 ;

孙强 .

计算机应用与软件, 2004, (12) :78-81

[2] 一种求受顶点数限制的最短路径的新算法 [J].

钟子飞 ;

黄水松 ;

伍磊 .

计算机工程与设计, 2004, (07) :1114-1115

[3] 最短路径的求解算法 [J].

徐凤生 .

计算机应用, 2004, (05) :88-89

[4] 求受顶点数限制的最短路径问题的一个算法 [J].

孙强 ;

杨宗源 .

计算机工程, 2002, (09) :73-74

[5] 求图中顶点之间所有最短路径的一种实用算法 [J].

孙强 ;

沈建华 ;

顾君忠 .

计算机工程, 2002, (02) :134-136

[6] 时间依赖的网络中最小时间路径算法 [J].

谭国真 ;

高文 .

计算机学报, 2002, (02) :165-172

[7] PC机群环境下最短路径并行算法的研究 [J].

谭国真 ;

隋春丽 .

小型微型计算机系统, 2001, (11) :1302-1304

[8]

算法设计与分析[M]. - 清华大学出版社 , 郑宗汉, 2005

← 1 →