摘要
论文针对数据组织结构导致Dijkstra算法的存储空间、邻接关系检索效率等关键问题,介绍了相关研究工作。并针对三维网格模型的邻接关系为稀疏图这一要点,基于三维网格模型的CSR存储结构,给出了记录Dijkstra最短路径的算法。该文算法返回了最短路径长度,记录最短路径上点集,充分利用了中间计算结果。
In this paper,we focus on the key problems of Dijkstra algorithm,memory and index of adjacency.After a brief introduction of related researches,we present a novel implementation of Dijkstra algorithm based on CSR data structure of 3D mesh model's sparse matrix adjacency.The length of the shortest path and the data set in the path is recoded,and the middle result is reused to save the computing source.
出处
《计算机工程与应用》
CSCD
北大核心
2005年第10期5-7,共3页
Computer Engineering and Applications
基金
国家973重点基础研究发展规划(编号:G2004CB318000)
国家863高技术研究发展计划项目(编号:2001AA231031
2002AA231021)
国家科技攻关计划课题奥运科技专项(编号:2001BA904B08)
中国科学院知识创新工程项目(编号:20006160
20016190(C))
