无回路网络中最短路问题的高效算法

• 作者: 冷洪泽 徐桢 谢政 陈挚
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 根 无回路网络 最短路树形图
• 年，卷（期）: 2009,（14）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 84-86,103
• 页数: 4页
• 分类号: TP311
• 字数: 4657字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2009.14.029

摘要

无回路网络是一类重要的网络,给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法.该算法将顶点进行重新编号,结合广度优先探索法,从源顶点出发依次搜索每个顶点的所有出弧,并在弧的头部进行权值变换操作,可以得到最短路树形图和任意顶点对间最短路,算法复杂度分别为O(m)和O(m(n-m1/2)).该算法思想简便、复杂度低、易于操作.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢政	国防科技大学理学院	40	115	6.0	9.0
2	徐桢	北京航空航天大学电子信息工程学院	18	125	5.0	10.0
3	陈挚	国防科技大学理学院	17	55	5.0	7.0
4	冷洪泽	国防科技大学理学院	3	3	1.0	1.0