买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉中山大学申请的专利用于计算大规模图上单源最短路径的并行Radius-Stepping方法和系统获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN114741183B 。

龙图腾网通过国家知识产权局官网在2025-11-14发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202210228944.9，技术领域涉及：G06F9/50；该发明授权用于计算大规模图上单源最短路径的并行Radius-Stepping方法和系统是由姚正安;王业智;王锦祥;施章灿设计研发完成，并于2022-03-08向国家知识产权局提交的专利申请。

本用于计算大规模图上单源最短路径的并行Radius-Stepping方法和系统在说明书摘要公布了：本发明公开一种用于计算大规模图上单源最短路径的并行Radius‑Stepping方法和系统，方法包括以下几个方面：在算法中预先将图数据中的顶点划分为若干个部分给相应的进程处理，确定需要进行处理的顶点集合后，各个进程分别处理对应部分的顶点进行处理，再对信息进行汇总。本发明利用多个进程并行处理对临时最短路径的更新，相较于串行的Radius‑Stepping算法，计算速度更快，进而提高在实际应用中的效率，提高了Radius‑Stepping算法在图数据规模过大的情况下的运行速度。

本发明授权用于计算大规模图上单源最短路径的并行Radius-Stepping方法和系统在权利要求书中公布了：1.一种用于计算大规模图上单源最短路径的并行Radius-Stepping方法，其特征在于，包括以下步骤： S1：对于待计算的大规模图，为所述大规模图中所有的顶点维护一个临时最短路径和一个集合S，集合S为所述大规模图中的点的子集合； S2：将所述大规模图中所有的顶点划分为若干部分分别分配给不同的子进程； S3：根据各顶点的临时最短路径、集合S和Radius函数计算临时最短路径上界，根据所述临时最短路径上界，筛选需要进行处理的顶点； S4：由各个子进程分别处理对应的顶点，得到更新后的临时最短路径； S5：由根进程汇总所有子进程处理后得到的更新后的临时最短路径，再传递给所有的子进程； S6：根据步骤S3计算得到的上界，更新集合S，判断是否继续循环，若继续，返回步骤S3；若不继续，输出所述大规模图中所有顶点的最短路径； 所述步骤S1中为所述大规模图中所有的顶点维护一个临时最短路径，具体为： 令源点的临时最短路径为0，其余顶点的初始临时最短路径设置为无穷大； 所述步骤S1中的集合S，具体为： 所述集合S在初始阶段只包含所述大规模图中的源点； 所述步骤S3中根据各顶点的临时最短路径、集合S和Radius函数计算临时最短路径上界，具体计算公式为： 式中，v表示顶点，δv表示顶点v的临时最短路径，rv表示顶点v为输入的radii函数，di表示临时最短路径上界，i表示迭代轮数； 所述步骤S3中筛选需要进行处理的顶点，若顶点的临时最短路径小于所述临时最短路径上界，则该点筛选为需要进行处理的顶点； 所述步骤S6中更新集合S，具体为： 集合S更新为临时最短路径小于所述最短路径上界的顶点v的集合； 所述步骤S6中判断是否继续循环，具体为： 判断所述大规模图中的所有顶点是否都在集合S中，如果是，判断为不继续循环，如果不是，判断为继续循环。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人中山大学，其通讯地址为：510275 广东省广州市海珠区新港西路135号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。

以上内容由龙图腾AI智能生成。