用O(tlogt)的连接图求有障碍时的最短路径

• 作者: 周智 陈国良 顾钧
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: VLSI设计 极区 自由区 强连接图 最短路径
• 年，卷（期）: 1999,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 519-524
• 页数: 6页
• 分类号: TP302
• 字数: 4207字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.1999.05.012

摘要

针对有障碍时求两点间的最短路径这一问题,提出了极区和自由区的概念,并由此构造出一种新的强连接图GF,它由自由区的特征边和障碍的极边构成,其顶点数为O(t),边数为O(tlogt),其中t为障碍的极边数.而现有最佳连通图的顶点数和边数为O(t2).同时提出了时间复杂度为O(tlog2t)的高效GF构造算法,并使用"不改向"的启发式A*算法在GF中寻找两点间的最短路径.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学技术系	123	2142	20.0	43.0
2	周智	中国科学技术大学计算机科学技术系	13	69	5.0	8.0
3	顾钧	香港科学技术大学计算机科学系	5	43	4.0	5.0