经过指定的中间节点集的最短路径算法

被引：19

作者：

黄书力

胡大裟

蒋玉明

机构：

[1] 四川大学计算机(软件)学院

来源：

计算机工程与应用 | 2015年 / 51卷 / 11期

关键词：

Dijkstra算法; 贪心算法; 动态规划; 最短路径; 相关节点;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

目前研究最短路径的算法,多数只是针对从起点出发到达终点的情况。如果限制这条最短路径必须要经过某些指定的中间节点,则现有的一些算法就不再适用了。基于Dijkstra算法和贪心理论,给出了解决此类问题的方法。将相关节点集拆分成三个子集,分别求连通三个子集的局部最短路径,进而形成全局待选最短路径,通过筛选得到目标路径。通过理论分析算法的时间复杂度和实际编程实验确认了该算法的有效性。

引用

收藏

页码：41 / 46

页数：6

相关论文

共 12 条

[1] 一种基于Dijkstra最短路径算法的改进算法 [J].

王智广 ;

王兴会 ;

李妍 .

内蒙古师范大学学报(自然科学汉文版), 2012, 41 (02) :195-200

[2] 适合复杂网络分析的最短路径近似算法 [J].

唐晋韬 ;

王挺 ;

王戟 .

软件学报, 2011, 22 (10) :2279-2290

[3] 智能交通中的高效多准最短路径混合算法 [J].

叶金平 ;

朱征宇 ;

王丽娜 ;

刘琳 .

计算机应用研究, 2011, 28 (09) :3301-3304

[4] Dijkstra最短路径算法优化策略 [J].

张锦明 ;

洪刚 ;

文锐 ;

王学涛 .

测绘科学, 2009, 34 (05) :105-106+99

[5] 北京奥运公交专线规划及评价方法 [J].

姚广铮 ;

孙壮志 ;

孙福亮 ;

刘新华 .

城市交通, 2008, (03) :29-34

[6] 求图中受顶点数限制的所有最短路径的算法 [J].

王卫强 ;

孙强 .

计算机工程与设计, 2008, (07) :1754-1757

[7] 求解最短路径的遗传算法中若干问题的讨论 [J].

徐庆征 ;

柯熙政 .

计算机工程与设计, 2008, (06) :1507-1509

[8] 动态网络最短路问题的复杂性与近似算法 [J].

林澜 ;

闫春钢 ;

蒋昌俊 ;

周向东 .

计算机学报, 2007, (04) :608-614

[9] Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用 [J].

王峰 ;

游志胜 ;

曼丽春 ;

高燕 ;

汤丽萍 .

计算机应用研究, 2006, (09) :203-205+208

[10] 前N条最短路径问题的算法及应用 [J].

柴登峰 ;

张登荣 .

浙江大学学报(工学版), 2002, (05) :61-64