一种求受顶点数限制的最短路径的新算法

被引：3

作者：

钟子飞

黄水松

伍磊

机构：

[1] 武汉大学计算机学院计算机科学系

[2] 武汉大学计算机学院计算机科学系武汉湖北

[3] 武汉湖北

来源：

关键词：

逆邻接表; 限制; 最短路径; 算法;

D O I：

10.16208/j.issn1000-7024.2004.07.025

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

提出了一种基于逆邻接表求受顶点数限制的最短路径的新算法,其时间复杂度为O((m-2)*w)(m是受限制的顶点数,w是有向图中弧的条数),优于同类算法。采用逆邻接表作为图的存储结构,该算法很容易实现。

引用

页码：1114 / 1115

页数：2