基于CSR存储的三维网格最短路径算法

A Shortest Path Algorithm Based-on Compressed Storage Format of 3D Mesh

论文针对数据组织结构导致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.