首页 | 本学科首页   官方微博 | 高级检索  
     

基于CSR存储的三维网格最短路径算法
引用本文:孙晓鹏,李华. 基于CSR存储的三维网格最短路径算法[J]. 计算机工程与应用, 2005, 41(10): 5-7
作者姓名:孙晓鹏  李华
作者单位:中国科学院计算技术研究所智能信息处理重点实验室,北京,100080;中国科学院研究生院,北京,100039;中国科学院计算技术研究所智能信息处理重点实验室,北京,100080
基金项目:国家973重点基础研究发展规划(编号:G2004CB318000),国家863高技术研究发展计划项目(编号:2001AA231031,2002AA231021),国家科技攻关计划课题奥运科技专项(编号:2001BA904B08),中国科学院知识创新工程项目(编号:20006160,20016190(C))
摘    要:论文针对数据组织结构导致Dijkstra算法的存储空间、邻接关系检索效率等关键问题,介绍了相关研究工作。并针对三维网格模型的邻接关系为稀疏图这一要点,基于三维网格模型的CSR存储结构,给出了记录Dijkstra最短路径的算法。该文算法返回了最短路径长度,记录最短路径上点集,充分利用了中间计算结果。

关 键 词:CSR存储结构  最短路径  Dijkstra算法  三维网格模型
文章编号:1002-8331-(2005)10-0005-03
修稿时间:2005-01-01

A Shortest Path Algorithm Based-on Compressed Storage Format of 3D Mesh
Sun Xiaopeng,Li Hua. A Shortest Path Algorithm Based-on Compressed Storage Format of 3D Mesh[J]. Computer Engineering and Applications, 2005, 41(10): 5-7
Authors:Sun Xiaopeng  Li Hua
Affiliation:Sun Xiaopeng1,2 Li Hua11
Abstract: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.
Keywords:CSR data structure  shortest path  Dijkstra algorithm  3D mesh model  
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号